#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
struct BigInt {
    vector<uint32_t> d;
    BigInt() {}
    BigInt(uint32_t v) { if (v) d.pb(v); }
};

int cmp(const BigInt& a, const BigInt& b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1;
    per(i, (int)a.d.size() - 1, 0) {
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    }
    return 0;
}

BigInt add(const BigInt& a, const BigInt& b) {
    BigInt c;
    uint64_t carry = 0;
    int n = max(a.d.size(), b.d.size());
    for (int i = 0; i < n || carry; ++i) {
        uint64_t sum = carry;
        if (i < a.d.size()) sum += a.d[i];
        if (i < b.d.size()) sum += b.d[i];
        c.d.pb(sum & 0xFFFFFFFF);
        carry = sum >> 32;
    }
    return c;
}

BigInt sub(const BigInt& a, const BigInt& b) {
    BigInt c;
    int64_t carry = 0;
    rep(i, 0, (int)a.d.size() - 1) {
        int64_t diff = a.d[i] - carry - (i < b.d.size() ? b.d[i] : 0);
        if (diff < 0) {
            diff += 0x100000000LL;
            carry = 1;
        } else carry = 0;
        c.d.pb(diff);
    }
    while (!c.d.empty() && c.d.back() == 0) c.d.pop_back();
    return c;
}

BigInt div_small(const BigInt& a, uint32_t b) {
    BigInt c;
    c.d.resize(a.d.size());
    uint64_t rem = 0;
    per(i, (int)a.d.size() - 1, 0) {
        rem = (rem << 32) + a.d[i];
        c.d[i] = rem / b;
        rem %= b;
    }
    while (!c.d.empty() && c.d.back() == 0) c.d.pop_back();
    return c;
}

BigInt shl(const BigInt& a, int shift) {
    if (a.d.empty()) return a;
    BigInt c;
    int words = shift / 32;
    int bits = shift % 32;
    c.d.assign(words, 0);
    uint64_t carry = 0;
    rep(i, 0, (int)a.d.size() - 1) {
        uint64_t val = ((uint64_t)a.d[i] << bits) + carry;
        c.d.pb(val & 0xFFFFFFFF);
        carry = val >> 32;
    }
    if (carry) c.d.pb(carry);
    return c;
}

char beats(char m) {
    if (m == 'P') return 'N';
    if (m == 'K') return 'P';
    return 'K';
}
namespace S1 {
    string role;
    ll n, T;
    ll tonum(char c) {
        if(c == 'P') return 0;
        if(c == 'K') return 1;
        return 2;
    }
    char tochar(ll x) {
        if(x == 0) return 'P';
        if(x == 1) return 'K';
        return 'N';
    }
    Ve<ll> encode(string s, ll len) {
        Ve<ll> res;
        while(s.find('1') != string :: npos) {
            ll r = 0;
            rep(i, 0, (ll)s.size() - 1) {
                ll v = r * 2 + (s[i] - '0');
                s[i] = v / 3 + '0', r = v % 3;
            }
            res.pb(r);
        }
        while(res.size() < len) res.pb(0);
        return res;
    }
    string decode(Ve<ll> s, ll len) {
        string res = "0";
        per(i, (ll)s.size() - 1, 0) {
            ll up = s[i];
            per(j, (ll)res.size() - 1, 0) {
                ll v = (res[j] - '0') * 3 + up;
                res[j] = v % 2 + '0', up = v / 2;
            }
            while(up) res.insert(res.begin(), up % 2 + '0'), up /= 2;
        }
        while(res.size() < len) res.insert(res.begin(), '0');
        return res;
    }
    void work(string role, int n, int T) {
        ll len = 0;
        string s(n, '1');
        while(s.find('1') != string :: npos) {
            ll r = 0;
            rep(i, 0, (ll)s.size() - 1) {
                ll v = r * 2 + (s[i] - '0');
                s[i] = v / 3 + '0', r = v % 3;
            }
            ++len;
        }
        auto solve = [&]() {
            cin >> s; Ve<ll> a = encode(s, len), b(len);
            ll d = 0, qa = 0, qb = 0;
            mt19937 rnd(108432);
            while(qa < len || qb < len) {
                ll o = 0, cur = rnd() % 3;
                if(!d) {
                    if(role[0] == 'A') {
                        if(qa < len) o = (a[qa] + cur) % 3;
                    }
                    else {
                        if(qb < len) o = (a[qb] + cur) % 3;
                    }
                }
                else if(d == 1) {
                    if(role[0] == 'A') o = 1;
                    else o = 0;
                }
                else {
                    if(role[0] == 'B') o = 1;
                    else o = 0;
                }
                cout << tochar(o) << endl;
                char oo; cin >> oo;
                ll to = tonum(oo);
                ll ma = (role[0] == 'A') ? o : to;
                ll mb = (role[0] == 'B') ? o : to;
                if(!d) {
                    if(role[0] == 'A' && qb < len) b[qb] = (to - cur + 3) % 3;
                    else if(role[0] == 'B' && qa < len) b[qa] = (to - cur + 3) % 3;
                    ++qa, ++qb;
                }
                if((mb - ma + 3) % 3 == 1) ++d;
                else if((ma - mb + 3) % 3 == 1) --d;
            }
            string ans = decode(b, n);
            cout << "! " << ans << endl;
        };
        while(T--) solve();
    }
}
void solve() {
    string role; cin >> role;
    bool isA = (role == "Algosia");
    int n, t; cin >> n >> t;
    if(n == 5) return S1 :: work(role, n, t), void();
    mt19937 rngA(108432), rngB(234801);
    BigInt TWO_10000 = shl(BigInt(1), 10000);
    while(t--) {
        string my_str;
        cin >> my_str;
        Ve<int> xA(n), xB(n);
        rep(i, 0, n - 1) xA[i] = rngA() & 1, xB[i] = rngB() & 1;
        rep(i, 0, n - 1) {
            if(isA) my_str[i] ^= xA[i];
            else my_str[i] ^= xB[i];
        }
        BigInt V;
        rep(i, 0, n - 1) {
            if (my_str[i] == '1') {
                int pos = 10000 + n - 1 - i;
                int word = pos / 32;
                int bit = pos % 32;
                if (V.d.size() <= word) V.d.resize(word + 1, 0);
                V.d[word] |= (1u << bit);
            }
        }

        BigInt LA = 0, RA = shl(BigInt(1), 15000);
        BigInt LB = 0, RB = RA;
        BigInt VA = isA ? V : BigInt(0);
        BigInt VB = !isA ? V : BigInt(0);

        int D = 0;

        while (true) {
            if (cmp(sub(RA, LA), TWO_10000) <= 0 && cmp(sub(RB, LB), TWO_10000) <= 0) break;

            char moves[] = {'P', 'K', 'N'};
            int pA[3] = {0, 1, 2}, pB[3] = {0, 1, 2};
            per(i, 2, 1) swap(pA[i], pA[rngA() % (i + 1)]);
            per(i, 2, 1) swap(pB[i], pB[rngB() % (i + 1)]);

            char mA = ' ', mB = ' ';
            BigInt WA = sub(RA, LA), WB = sub(RB, LB);
            int sA = -1, sB = -1;

            if (D == 0) {
                BigInt WA3 = div_small(WA, 3), P1A = add(LA, WA3), P2A = add(P1A, WA3);
                BigInt WB3 = div_small(WB, 3), P1B = add(LB, WB3), P2B = add(P1B, WB3);

                if (isA) sA = (cmp(VA, P1A) < 0) ? 0 : ((cmp(VA, P2A) < 0) ? 1 : 2);
                if (!isA) sB = (cmp(VB, P1B) < 0) ? 0 : ((cmp(VB, P2B) < 0) ? 1 : 2);

                if (isA) mA = moves[pA[sA]];
                if (!isA) mB = moves[pB[sB]];
            } else if (D == 1) {
                mA = moves[pA[0]];
                char v[] = {mA, beats(mA)};
                BigInt WB4 = div_small(WB, 4), P1B = add(LB, WB4);

                if (!isA) {
                    sB = (cmp(VB, P1B) < 0) ? 0 : 1;
                    mB = v[sB];
                }
            } else { 
                mB = moves[pB[0]];
                char v[] = {mB, beats(mB)};
                BigInt WA4 = div_small(WA, 4), P1A = add(LA, WA4);

                if (isA) {
                    sA = (cmp(VA, P1A) < 0) ? 0 : 1;
                    mA = v[sA];
                }
            }

            if (isA) { cout << mA << endl; cin >> mB; } 
            else { cout << mB << endl; cin >> mA; }

            if (D == 0) {
                rep(i, 0, 2) if (moves[pA[i]] == mA) sA = i;
                rep(i, 0, 2) if (moves[pB[i]] == mB) sB = i;
                
                BigInt WA3 = div_small(WA, 3), P1A = add(LA, WA3), P2A = add(P1A, WA3);
                if (sA == 0) RA = P1A;
                else if (sA == 1) { LA = P1A; RA = P2A; }
                else LA = P2A;

                BigInt WB3 = div_small(WB, 3), P1B = add(LB, WB3), P2B = add(P1B, WB3);
                if (sB == 0) RB = P1B;
                else if (sB == 1) { LB = P1B; RB = P2B; }
                else LB = P2B;
            } else if (D == 1) {
                char v[] = {moves[pA[0]], beats(moves[pA[0]])};
                sB = (mB == v[0]) ? 0 : 1;
                BigInt WB4 = div_small(WB, 4), P1B = add(LB, WB4);
                if (sB == 0) RB = P1B; else LB = P1B;
            } else {
                char v[] = {moves[pB[0]], beats(moves[pB[0]])};
                sA = (mA == v[0]) ? 0 : 1;
                BigInt WA4 = div_small(WA, 4), P1A = add(LA, WA4);
                if (sA == 0) RA = P1A; else LA = P1A;
            }

            int delta = 0;
            if (mA == 'P' && mB == 'K') delta = 1;
            else if (mA == 'K' && mB == 'N') delta = 1;
            else if (mA == 'N' && mB == 'P') delta = 1;
            else if (mA == 'K' && mB == 'P') delta = -1;
            else if (mA == 'N' && mB == 'K') delta = -1;
            else if (mA == 'P' && mB == 'N') delta = -1;
            D += delta;
        }

        BigInt SA = div_small(add(LA, sub(TWO_10000, BigInt(1))), 1);
        BigInt SB = div_small(add(LB, sub(TWO_10000, BigInt(1))), 1);

        auto extract_bits = [&](BigInt target) {
            string res = "";
            rep(i, 0, n - 1) {
                int pos = 10000 + n - 1 - i;
                int word = pos / 32, bit = pos % 32;
                res += (word < target.d.size() && (target.d[word] & (1u << bit))) ? '1' : '0';
            }
            return res;
        };
        string ans;
        if (isA) ans = extract_bits(SB);
        else ans = extract_bits(SA);
        rep(i, 0, n - 1) {
            if(isA) ans[i] ^= xB[i];
            else ans[i] ^= xA[i];
        }
        cout << "! " << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}