Subtask 1: (~100 \le Q \le 2499~)

Ta sẽ lần lượt tìm các kí tự kế tiếp bắt đầu từ vị trí ~0~. Số truy vấn thực hiện tối đa sẽ là ~\frac{52*51}{20}~.

Subtask 2: (~50 \le Q \le 99~)

Để tối ưu việc tìm các kí tự kế tiếp, bước đầu tiên chúng ta sẽ thực hiện các truy vấn có dạng \t{"? P[0]{c}"} với ~c~ là một kí tự Latin.

• Nếu truy vấn ? P[0]{c} trả về xâu kí tự ~c~ thì ~pos[c]=1~.
• Nếu truy vấn ? P[0]{c} trả về xâu kí tự ~P[1]~ thì ~pos[c]=2~.
• ...

Tuy nhiên ta thấy rằng với truy vấn thực hiện như trên với ~c=P[3]~ hoặc ~c=P[4]~ thì đều sẽ trả về xâu kí tự ~P[2]~. Vì vậy ở bước thứ ~2~, ta cần phải phân biệt hai kí tự trên bằng cách sử dụng một truy vấn có dạng ? {c}P[0] với ~c~ là \bf{một} trong hai kí tự trên cần phân biệt. Nếu truy vấn trên trả về xâu kí tự ~P[2]~ thì ~pos[c]=4~, còn ngược lại thì ~pos[c]=3~. Thực hiện tương tự với cặp kí tự ~\{P[5],P[6]\}~, ~\{P[7],P[8]\}~, ~\ldots~, ~\{P[50],P[51]\}~.

Số truy vấn thực hiện tối đa ở bước thứ nhất là ~51~ truy vấn, ở bước thứ ~2~ là ~24~ truy vấn. Vì vậy tổng số truy vấn thực hiện tối đa sẽ là ~75~ truy vấn. Để tối ưu số truy vấn cần thực hiện, ta sẽ thực hiện truy vấn có dạng ? P[0]{x}P[0]P[0]P[0]P[0]P[0]P[0]P[0]{y} để lấy thông tin cho cả hai kí tự ~x~ và ~y~ trong một lượt thực hiện. Khi đó số truy vấn thực hiện tối đa ở bước thứ nhất sẽ giảm xuống còn ~26~ truy vấn, và tổng số truy vấn thực hiện tối đa ở cả ~2~ bước là ~50~ truy vấn.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

int to_int(char c){
    if (isupper(c)){
        return c - 'A';
    }
    else{
        return c - 'a' + 26;
    }
}

char to_char(int x){
    if (x < 26){
        return x + 'A';
    }
    else{
        return x - 26 + 'a';
    }
}

const int N = 52;

vector <int> query(const vector <int>& a){
    cout << "? ";
    for (auto x: a){
        cout << to_char(x);
    }
    cout << endl;
    vector <int> b;
    for (int i = 0; i < ssize(a); i++){
        char c;
        cin >> c;
        b.emplace_back(to_int(c));
    }
    return b;
}

void answer(const array <int, N>& ans){
    cout << "! ";
    for (auto x: ans){
        cout << to_char(x);
    }
    cout << endl;
    exit(0);
}

array <int, N> ans;
array <int, N> pos;

void set_ans(int i, int x){
    ans[i] = x;
    pos[x] = i;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ans.fill(-1);
    pos.fill(-1);

    {
        char c;
        cin >> c;
        set_ans(0, to_int(c));
    }

    array <int, N> A0_x;
    array <vector <int>, N> adj;
    int root = -1;
    // Find A0_x and adj
    {
        A0_x.fill(-1);
        int x1 = -1, x2 = -1;
        for (int x = 0; x < N; x++){
            if (pos[x] != -1){
                continue;
            }
            if (x1 == -1){
                x1 = x;
                continue;
            }
            x2 = x;
            vector <int> cur = query({
                ans[0], x1,
                ans[0], ans[0], ans[0], ans[0], ans[0], ans[0], ans[0],
                x2
            });
            A0_x[x1] = cur[1];
            A0_x[x2] = cur.back();
            x1 = x2 = -1;
        }
        if (x1 != -1){
            A0_x[x1] = query({ans[0], x1}).back();
        }
        for (int x = 0; x < N; x++){
            if (pos[x] != -1){
                continue;
            }
            if (A0_x[x] == x){
                root = x;
                set_ans(1, x);
                continue;
            }
            adj[A0_x[x]].emplace_back(x);
        }
    }
    array <int, N> sub;
    sub.fill(-1);
    // DFS
    {
        auto dfs = [&](auto self, int u) -> void {
            sub[u] = 1;
            for (auto v: adj[u]){
                self(self, v);
                sub[u] += sub[v];
            }
        };
        dfs(dfs, root);
    }
    // Find ans[1, 2], ans[3, 4], ans[5, 6], ..., ans[9, 10]
    {
        for (int i1 = 1, i2 = 2; i2 <= 10; i1 += 2, i2 += 2){
            int im = i2 / 2;
            vector <int> xs;
            for (int x = 0; x < N; x++){
                // if (pos[x] != -1){
                //  continue;
                // }
                if (A0_x[x] == ans[im]){
                    xs.emplace_back(x);
                }
            }
            assert(ssize(xs) == 2);
            if (sub[xs.front()] != sub[xs.back()]){
                if (sub[xs.front()] > sub[xs.back()]){
                    set_ans(i1, xs.front());
                    set_ans(i2, xs.back());
                }
                else{
                    set_ans(i1, xs.back());
                    set_ans(i2, xs.front());
                }
                continue;
            }
            if (query({ans[i1 - 1], xs.front()}).back() == xs.front()){
                set_ans(i1, xs.front());
                set_ans(i2, xs.back());
            }
            else{
                set_ans(i1, xs.back());
                set_ans(i2, xs.front());
            }
        }
    }
    // Find ans[11..20], ans[21..30], ..., ans[41..50]
    {
        for (int l = 11, r = 20; r <= 50; l += 10, r += 10){
            vector <vector <int>> xs(10 / 2);
            for (int im = (l + 1) / 2; im <= (r + 1) / 2; im++){
                for (int x = 0; x < N; x++){
                    if (pos[x] != -1){
                        continue;
                    }
                    if (A0_x[x] == ans[im]){
                        xs[im - (l + 1) / 2].emplace_back(x);
                    }
                }
            }
            vector <int> cur = query({
                ans[l - 1],
                xs[0].front(), xs[0].front(),
                xs[1].front(), xs[1].front(),
                xs[2].front(), xs[2].front(),
                xs[3].front(), xs[3].front(),
                xs[4].front()
            });
            int i = l - 1;
            for (int j = 0, jcur = 1, i1 = l, i2 = l + 1; i2 <= r; j++, jcur += 2, i1 += 2, i2 += 2){
                if (i + 1 == i1){
                    if (cur[jcur] == xs[j].front()){
                        set_ans(i1, xs[j].front());
                        set_ans(i2, xs[j].back());
                    }
                    else{
                        set_ans(i1, xs[j].back());
                        set_ans(i2, xs[j].front());
                    }
                }
                else{
                    if (cur[jcur] == ans[i + 1]){
                        set_ans(i1, xs[j].front());
                        set_ans(i2, xs[j].back());
                    }
                    else{
                        set_ans(i1, xs[j].back());
                        set_ans(i2, xs[j].front());
                    }
                }
                i = pos[xs[j].front()];
            }
        }
    }
    // Find ans[51]
    {
        for (int x = 0; x < N; x++){
            if (pos[x] != -1){
                continue;
            }
            set_ans(N - 1, x);
        }
    }

    answer(ans);
}