using namespace std;
int main(void)
{
    int q, n;
    char c;
    string s, qtype;
    set<pair<char, int>> sorted_string;
    cin >> s;
    cin >> q;
    n = s.size();
    for (int i = 0; i < n; ++i)
        sorted_string.emplace(s[i], i);
    vector<pair<int, bool>> ans;
    ans.emplace_back(-1, true);
    while (q--)
    {
        cin >> qtype;
        if (qtype[1] == 'u')
        {
            cin >> c;
            auto it = sorted_string.upper_bound({c, ans.back().first});
            if (it != sorted_string.end() and c == it->first)
                ans.emplace_back(it->second, ans.back().second);
            else
                ans.emplace_back(ans.back().first, false);
        }
        else
            ans.pop_back();
        cout << (ans.back().second ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
using predicate = function<bool(int)>;
int const NMAX = 2e5 + 11;
int n, m, a[NMAX];
bool ok(int n_convinced)
{
    int reviews = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > reviews and n_convinced > 0)
        {
            n_convinced--;
            reviews++;
        }
        else if (a[i] <= reviews)
            reviews++;
    }
    return reviews >= m;
}
int bs(int l, int r, predicate p)
{
    while (l < r)
    {
        int m = l + (r - l) / 2;
        if (p(m))
            r = m;
        else
            l = m + 1;
    }
    return l;
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << bs(0, n, ok) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int const AMAX = 2e5 + 11;
int cnt[AMAX];
int main(void)
{
    int n, ai, pairs = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> ai;
        cnt[ai]++;
        if (cnt[ai] % 2 == 0)
            pairs++;
    }
    cout << pairs / 2 << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, l = -1, r = -1;
    string s, t;
    cin >> s >> t;
    n = s.size();
    for (int i = 0; i < n; ++i)
    {
        if (s[i] != t[i])
        {
            l = i;
            break;
        }
    }
    for (int i = n - 1; i >= 0; --i)
    {
        if (s[i] != t[i])
        {
            r = i;
            break;
        }
    }
    if (l != -1 and r != -1)
    {
        for (int i = 0; i < r - l + 1; ++i)
        {
            if (s[l + i] != t[r - i])
            {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using iii = array<int, 3>;
int main(void)
{
    int n, last_close = 0, cnt = 0;
    vi s, e, ans;
    vector<iii> events;
    cin >> n;
    s.resize(n);
    e.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i] >> e[i];
        events.push_back({s[i], -1, i});
        events.push_back({e[i], +1, i});
    }
    sort(events.begin(), events.end());
    for (auto [t, sign, i] : events)
    {
        if (sign == -1)
            ++cnt;
        else if (sign == +1 and s[i] > last_close)
        {
            ans.push_back(t);
            last_close = t;
            cnt = 0;
        }
    }
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

using namespace std;
using vs = vector<string>;
const int CMAX = 26;
struct node
{
    node * children[CMAX];
    set<int> matches;
    set<int> terminated;
    node() { memset(children, 0, sizeof(children)); }
};
int n;
vs v;
node *trie;
void insert(int ix, const string &s)
{
    int cix;
    node *x = trie;
    x->matches.insert(ix);
    for (auto const c : s)
    {
        cix = c - 'a';
        if (x->children[cix] == nullptr)
            x->children[cix] = new node();
        x = x->children[cix];
        x->matches.insert(ix);
    }
    x->terminated.insert(ix);
}
node *remove(int ix, const string &s, int s_ix, node *x)
{
    if (x == nullptr)
        return nullptr;
    x->matches.erase(ix);
    if (s_ix < (int)s.size())
    {
        int cix = s[s_ix] - 'a';
        x->children[cix] = remove(ix, s, s_ix + 1, x->children[cix]);
    }
    if (s_ix == (int)s.size())
        x->terminated.erase(ix);
    if (x->matches.empty())
    {
        delete (x);
        x = nullptr;
    }
    return x;
}
void update(int ix, const string &s)
{
    string t = v[ix];
    trie = remove(ix, t, 0, trie);
    if (trie == nullptr)
        trie = new node();
    insert(ix, s);
    v[ix] = s;
}
bool in_range(const set<int> &si, int l, int r)
{
    auto it = si.lower_bound(l);
    if (it != si.end() and *it <= r)
        return true;
    else
        return false;
}
bool q2(int l, int r, const string &s)
{
    int cix;
    node *x = trie;
    for (auto const c : s)
    {
        cix = c - 'a';
        if (not x->terminated.empty() and in_range(x->terminated, l, r))
            return true;
        else if (x->children[cix] == nullptr)
            return false;
        x = x->children[cix];
    }
    if (not x->terminated.empty() and in_range(x->terminated, l, r))
        return true;
    return false;
}
bool q3(int l, int r, const string &s)
{
    int cix;
    node *x = trie;
    for (auto const c : s)
    {
        cix = c - 'a';
        if (x->children[cix] == nullptr)
            return false;
        x = x->children[cix];
    }
    return in_range(x->matches, l, r);
}
int main(void)
{
    string s;
    int q, type, i, l, r;
    cin >> n;
    v.resize(n);
    trie = new node();
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
        insert(i, v[i]);
    }
    cin >> q;
    while (q--)
    {
        cin >> type;
        if (type == 1)
        {
            cin >> i >> s;
            update(i - 1, s);
        }
        else if (type == 2)
        {
            cin >> l >> r >> s;
            cout << (q2(l - 1, r - 1, s) ? "Y" : "N") << endl;
        }
        else if (type == 3)
        {
            cin >> l >> r >> s;
            cout << (q3(l - 1, r - 1, s) ? "Y" : "N") << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
const int NMAX = 5e4;
bitset<NMAX> mark;
vll primes;
void sieve(ll upperbound)
{
    mark.set();
    mark[0] = mark[1] = 0;
    for (ll i = 2; i < upperbound; ++i)
    {
        if (mark[i])
        {
            for (ll j = i * i; j < upperbound; j += i)
                mark[i] = 0;
            primes.push_back(i);
        }
    }
}
pair<pii, pii> solve(ll l, ll r)
{
    vll is_prime(r - l + 1, true);
    ll cur, prev;
    pii mindist, maxdist;
    for (auto p : primes)
    {
        ll start = max(p * p, (l + p - 1) / p * p);
        if (start > r)
            continue;
        for (ll j = start; j <= r; j += p)
            is_prime[j - l] = false;
    }
    if (l == 1)
        is_prime[0] = false;
    mindist = make_pair(0, INT_MAX);
    maxdist = make_pair(0, 0);
    cur = prev = -1;
    for (int i = 0; i <= r - l; ++i)
    {
        if (is_prime[i])
        {
            cur = l + i;
            if (cur == -1)
                continue;
            if (prev == -1)
            {
                prev = cur;
                continue;
            }
            if (cur - prev < mindist.second - mindist.first)
            {
                mindist.first = prev;
                mindist.second = cur;
            }
            if (cur - prev > maxdist.second - maxdist.first)
            {
                maxdist.first = prev;
                maxdist.second = cur;
            }
            prev = cur;
        }
    }
    return make_pair(mindist, maxdist);
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int l, r;
    sieve(NMAX);
    while (cin >> l >> r)
    {
        pair<pii, pii> ans = solve(l, r);
        if (ans.second.first == 0 and ans.second.second == 0)
            cout << "There are no adjacent primes." << endl;
        else
            cout << ans.first.first << ',' << ans.first.second
                 << " are closest, " << ans.second.first << ','
                 << ans.second.second << " are most distant." << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
const int NMAX = 1e7 + 11;
vector<int> prime;
bitset<NMAX> is_prime;
void sieve(ll n)
{
    ll sieve_size = n + 1;
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i <= sieve_size; ++i)
    {
        if (is_prime[i])
        {
            prime.push_back(i);
            for (ll j = i * i; j <= sieve_size; j += i)
                is_prime[j] = 0;
        }
    }
}
bool solve(ll n, ll m)
{
    if (m == 0)
        return true;
    ll i = 0, pf = prime[i], pf2, count1, count2;
    while (pf * pf <= m)
    {
        count1 = count2 = 0;
        while (m % pf == 0)
        {
            ++count1;
            m /= pf;
        }
        pf2 = pf;
        while (pf2 <= n)
        {
            count2 += n / pf2;
            pf2 *= pf;
        }
        if (count2 < count1)
            return false;
        pf = prime[i++];
    }
    if (m != 1)
    {
        if (n < m)
            return false;
    }
    return true;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve(NMAX);
    ll n, m;
    while (cin >> n >> m)
    {
        cout << m << " ";
        if (solve(n, m))
            cout << "divides ";
        else
            cout << "does not divide ";
        cout << n << "!\n";
    }
    return 0;
}

using namespace std;
using iii = tuple<int, int, int>;
using ii = pair<int, int>;
const int NMAX = 1e5 + 11;
int n;
bool vis[NMAX];
iii wsi[NMAX];
ii dp[NMAX];
void reconstruct(int i)
{
    if (i == -1)
        return;
    reconstruct(dp[i].second);
    cout << get<2>(wsi[i]) + 1 << endl;
}
void solve(void)
{
    sort(wsi, wsi + n);
    for (int i = 0; i < n; ++i)
    {
        dp[i].second = -1;
        for (int j = 0; j < i; ++j)
        {
            if (get<1>(wsi[j]) > get<1>(wsi[i]) and
                get<0>(wsi[j]) < get<0>(wsi[i]))
            {
                if (dp[i].first < dp[j].first)
                    dp[i] = make_pair(dp[j].first, j);
            }
        }
        dp[i].first += 1;
    }
    int lasti, lastv = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        if (lastv < dp[i].first)
        {
            lasti = i;
            lastv = dp[i].first;
        }
    }
    cout << lastv << endl;
    reconstruct(lasti);
}
int main(void)
{
    int i = 0, w, s;
    while (cin >> w >> s)
    {
        wsi[i] = make_tuple(w, s, i);
        ++i;
    }
    n = i;
    solve();
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e3 + 11;
const int MWMAX = 30 + 11;
int n, g;
int p[NMAX], w[NMAX], mem[NMAX][MWMAX];
int dp(int pos, int capacity)
{
    int &ans = mem[pos][capacity];
    if (pos == n)
        return 0;
    if (ans != -1)
        return ans;
    if (capacity - w[pos] >= 0)
        ans = dp(pos + 1, capacity - w[pos]) + p[pos];
    return (ans = max(ans, dp(pos + 1, capacity)));
}
int main(void)
{
    int t, mw;
    cin >> t;
    while (t--)
    {
        ll ans = 0;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> p[i] >> w[i];
        cin >> g;
        for (int i = 0; i < n; ++i)
            memset(mem[i], -1, MWMAX * sizeof(int));
        for (int i = 0; i < g; ++i)
        {
            cin >> mw;
            ans += dp(0, mw);
        }
        cout << ans << endl;
    }
    return 0;
}