using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
vi prefix_function(string s)
{
    int n = (int)s.size();
    vi pi(n, 0);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        string str, pat;
        cin >> str >> pat;
        int pat_sz = (int)pat.size();
        auto pi = prefix_function(pat + "#" + str);
        vi ans;
        for (int i = pat_sz + 1, len = (int)pi.size(); i < len; ++i)
            if (pi[i] == pat_sz)
                ans.push_back(i + 1 - 2 * pat_sz);
        if ((int)ans.size() == 0)
            cout << "Not Found" << endl;
        else
            cout << (int)ans.size() << endl, write(ans.begin(), ans.end(), " "), cout << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int const NMAX = 5e5 + 11;
int n, pi[NMAX];
char s[NMAX];
int prefix_function(string s)
{
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi[n - 1];
}
int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int k;
        scanf("%s %d", s, &k);
        n = strlen(s);
        int x = prefix_function(s);
        printf("%lld\n", ll(k - 1) * ll(n - x) + n);
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
struct FenwickTree2D
{
    vector<vector<int>> bit;
    int n, m;
    FenwickTree2D(vector<vector<int>> a)
    {
        n = (int)a.size(), m = (int)a.front().size();
        bit.assign(n, vi(m, 0));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                add(i, j, a[i][j]);
    }
    int sum(int x, int y)
    {
        int ret = 0;
        for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
            for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
                ret += bit[i][j];
        return ret;
    }
    void add(int x, int y, int delta)
    {
        for (int i = x; i < n; i = i | (i + 1))
            for (int j = y; j < m; j = j | (j + 1))
                bit[i][j] += delta;
    }
    int query(int y1, int x1, int y2, int x2)
    {
        auto ans = sum(x2, y2);
        if (x1 > 0)
            ans -= sum(x1 - 1, y2);
        if (y1 > 0)
            ans -= sum(x2, y1 - 1);
        if (x1 > 0 and y1 > 0)
            ans += sum(x1 - 1, y1 - 1);
        return ans;
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<vi> a(n, vi(n));
    for (int row = 0; row < n; ++row)
    {
        for (int col = 0; col < n; ++col)
        {
            char ch;
            cin >> ch;
            a[row][col] = ch == '*';
        }
    }
    FenwickTree2D tree(a);
    while (q--)
    {
        int y1, x1, y2, x2;
        cin >> x1 >> y1 >> x2 >> y2;
        y1--, x1--, y2--, x2--;
        if (x1 > x2)
            swap(x1, x2);
        if (y1 > y2)
            swap(y1, y2);
        cout << tree.query(y1, x1, y2, x2) << endl;
    }
    return 0;
}

using namespace std;
int main(void)
{
    long long n;
    cin >> n;
    while (n != 1)
    {
        cout << n << " ";
        n = (n % 2 == 0 ? n / 2 : 3 * n + 1);
    }
    cout << n;
    return 0;
}

using namespace std;
int main(void)
{
    int u, v;
    vector<int> deg(5, 0);
    for (int i = 0; i < 3; ++i)
    {
        cin >> u >> v;
        ++deg[u], ++deg[v];
    }
    int ones = 2;
    int evens = 2;
    for (int i = 1; i < 5; ++i)
    {
        if (deg[i] == 1)
            --ones;
        else if (deg[i] % 2 == 0)
            --evens;
    }
    if (ones == 0 and evens == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int const INF = 1e9;
int main(void)
{
    int n;
    string s;
    vi pw, pb;
    cin >> n >> s;
    s = ' ' + s;
    pw.resize(n + 1, 0), pb.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        pw[i] = pw[i - 1] + (s[i] == '.');
        pb[i] = pb[i - 1] + (s[i] == '#');
    }
    int ans = INF, left, right;
    for (int i = 1; i <= n - 1; ++i)
    {
        left = pb[i], right = (pw[n] - pw[i]);
        ans = min(ans, left + right);
    }
    ans = min({ans, n - pb[n], n - pw[n]});
    cout << ans << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
const int INF = 1e9 + 11;
int n, seg[4 * NMAX], a[NMAX];
void build(int a[], int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    }
}
int query(int v, int tl, int tr, int ql, int qr)
{
    if (ql > qr)
        return INF;
    else if (ql == tl and qr == tr)
        return seg[v];
    else
    {
        int tm = (tl + tr) / 2;
        return min(query(2 * v, tl, tm, ql, min(tm, qr)),
                   query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
}
int main(void)
{
    int t, q, l, r;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc)
    {
        cin >> n >> q;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        memset(seg, 0, sizeof(seg));
        build(a, 1, 0, n - 1);
        cout << "Scenario #" << tc << ":" << endl;
        while (q--)
        {
            cin >> l >> r;
            if (l > r)
                swap(l, r);
            cout << query(1, 0, n - 1, l - 1, r - 1) << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
using iii = tuple<int, int, int>;
using vi = vector<int>;
const int NMAX = 1e4 + 11;
int n, parent[NMAX], depth[NMAX], heavy[NMAX], head[NMAX], pos[NMAX], hldcnt;
int cost[NMAX];
vi g[NMAX];
iii edges[NMAX];
struct segtree
{
    int n;
    int t[4 * NMAX];
    segtree() {}
    segtree(int n) : n(n) {}
    void build(int a[]) { build_util(a, 1, 0, n - 1); }
    void build_util(int a[], int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = cost[tl];
        else
        {
            int tm = (tl + tr) >> 1;
            build_util(a, (v << 1), tl, tm);
            build_util(a, (v << 1) + 1, tm + 1, tr);
            t[v] = ((t[v << 1]) > (t[(v << 1) + 1]) ? (t[v << 1]) : (t[(v << 1) + 1]));
        }
    }
    int query(int ql, int qr) { return query_util(1, 0, n - 1, ql, qr); }
    int query_util(int v, int tl, int tr, int ql, int qr)
    {
        if (ql > qr)
            return 0;
        if (ql == tl and qr == tr)
            return t[v];
        int tm = (tl + tr) >> 1;
        int rl = query_util((v << 1), tl, tm, ql, min(tm, qr));
        int rr = query_util((v << 1) + 1, tm + 1, tr, max(tm + 1, ql), qr);
        return ((rl) > (rr) ? (rl) : (rr));
    }
    void update(int pos, int new_val)
    {
        update_util(1, 0, n - 1, pos, new_val);
    }
    void update_util(int v, int tl, int tr, int pos, int new_val)
    {
        if (tl > pos or tr < pos)
            return;
        if (tl == tr and tl == pos)
            t[v] = new_val;
        else
        {
            int tm = (tl + tr) >> 1;
            update_util(v << 1, tl, tm, pos, new_val);
            update_util((v << 1) + 1, tm + 1, tr, pos, new_val);
            t[v] = ((t[v << 1]) > (t[(v << 1) + 1]) ? (t[v << 1]) : (t[(v << 1) + 1]));
        }
    }
} st;
int dfs(int u)
{
    int usz = 1, mvz = 0, vsz;
    for (auto v : g[u])
    {
        if (v != parent[u])
        {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            vsz = dfs(v);
            usz += vsz;
            if (vsz > mvz)
            {
                mvz = vsz;
                heavy[u] = v;
            }
        }
    }
    return usz;
}
void decompose(int u, int h)
{
    head[u] = h;
    pos[u] = hldcnt++;
    if (heavy[u] != -1)
        decompose(heavy[u], h);
    for (auto v : g[u])
    {
        if (parent[u] != v and heavy[u] != v)
            decompose(v, v);
    }
}
void update(int i, int new_value)
{
    auto uvc = edges[i];
    int u = get<0>(uvc);
    int v = get<1>(uvc);
    if (depth[u] > depth[v])
        swap(u, v);
    st.update(pos[v], new_value);
}
int query(int u, int v)
{
    int ans = 0;
    while (head[u] != head[v])
    {
        if (depth[head[u]] > depth[head[v]])
            swap(u, v);
        ans = ((ans) > (st.query(pos[head[v]], pos[v])) ? (ans) : (st.query(pos[head[v]], pos[v])));
        v = parent[head[v]];
    }
    if (depth[u] > depth[v])
        swap(u, v);
    return ((ans) > (st.query(pos[u] + 1, pos[v])) ? (ans) : (st.query(pos[u] + 1, pos[v])));
}
void reset(void)
{
    hldcnt = 0;
    memset(heavy, -1, sizeof(*heavy) * n);
    for (int i = 0; i < n; ++i)
        g[i].clear();
}
int main(void)
{
    char s[10];
    int t, u, v, c, ei, nv;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        st = segtree(n);
        reset();
        for (int i = 0; i < n - 1; ++i)
        {
            scanf("%d %d %d", &u, &v, &c);
            edges[i] = make_tuple(u - 1, v - 1, c);
            g[u - 1].push_back(v - 1);
            g[v - 1].push_back(u - 1);
        }
        dfs(0);
        decompose(0, 0);
        for (int i = 0; i < n - 1; ++i)
        {
            auto uvc = edges[i];
            u = get<0>(uvc);
            v = get<1>(uvc);
            c = get<2>(uvc);
            if (depth[u] > depth[v])
                swap(u, v);
            cost[pos[v]] = c;
        }
        st.build(cost);
        while (scanf("%s", s) and s[0] != 'D')
        {
            if (s[0] == 'Q')
            {
                scanf("%d %d", &u, &v);
                printf("%d\n", query(u - 1, v - 1));
            }
            else
            {
                scanf("%d %d", &ei, &nv);
                update(ei - 1, nv);
            }
        }
    }
    return 0;
}

using namespace std;
using iii = array<int, 3>;
const int NMAX = 1e5 + 11;
int n;
int lazy[4 * NMAX];
iii seg[4 * NMAX];
void lazy_propagate(int v, int tl, int tr, int delta)
{
    iii temp(seg[v]);
    int last = (0 - delta % 3 + 3) % 3;
    for (int i = 0; i < 3; ++i)
    {
        seg[v][i] = temp[last];
        last = (last + 1) % 3;
    }
    if (tl != tr)
    {
        lazy[2 * v] += delta;
        lazy[2 * v + 1] += delta;
    }
    lazy[v] = 0;
}
inline iii merge(iii a, iii b)
{
    return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
void update(int v, int tl, int tr, int ql, int qr, int delta)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return;
    if (ql == tl and qr == tr)
        lazy_propagate(v, tl, tr, delta);
    else
    {
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, ql, min(qr, tm), delta);
        update(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr, delta);
        seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
    }
}
iii query(int v, int tl, int tr, int ql, int qr)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return {0, 0, 0};
    if (ql == tl and qr == tr)
        return seg[v];
    else
    {
        int tm = (tl + tr) / 2;
        return merge(query(2 * v, tl, tm, ql, min(tm, qr)),
                     query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = {1, 0, 0};
    else
    {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
    }
}
int main(void)
{
    int q, type, ql, qr;
    cin >> n >> q;
    build(1, 0, n - 1);
    while (q--)
    {
        cin >> type >> ql >> qr;
        if (type == 0)
        {
            update(1, 0, n - 1, ql, qr, +1);
        }
        else
        {
            auto [r0, r1, r2] = query(1, 0, n - 1, ql, qr);
            cout << r0 << endl;
        }
    }
    return 0;
}

using namespace std;
int main(void)
{
    int op, n, price;
    string stock, s;
    set<pair<int, string>> stocks;
    map<string, int> stockprice;
    cin >> n;
    for (int day = 1; day <= n; ++day)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> stock >> price;
            stockprice[stock] = price;
            stocks.insert({price, stock});
        }
        else if (op == 2)
        {
            cin >> stock >> price;
            stocks.erase({stockprice[stock], stock});
            stocks.insert({price, stock});
            stockprice[stock] = price;
        }
        else if (op == 3)
        {
            cin >> s;
            auto [price, stock] = *stocks.begin();
            cout << stock << " " << day << endl;
            stocks.erase(stocks.begin());
        }
    }
    return 0;
}