#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) X.begin(), X.end()
#define sz(X) int(size(X))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
using pii = pair<int, int>; using vi = vector<int>;
using ll = long long; using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) { *(int *)0 = 0; });
#define DTP(x, y) auto operator<<(auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; }
auto operator<<(auto &o, auto a) -> decltype(all(a), o);
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
#define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", [](auto... arg_) { (( cerr << arg_ << ", " ), ...) << '\n'; }(x)
#else
#define deb(...) 0
#endif

const int BITS = 50, WORDS = 100;
const ll BASE = 1LL << BITS;

struct bigint_t {
    array<ll, WORDS> words{};

    bigint_t() {}
    bigint_t(const string &s) {
        rep(i, sz(s)) {
            if (s[i] == '0') {}
            else if (s[i] == '1') xorbit(i);
            else assert(false);
        }
    }

    bool iszero() {
        return *max_element(all(words)) == 0;
    }
    void fillrandom(mt19937_64 &rnd) {
        for (auto &a : words) a = rnd() % BASE;
    }
    bool getbit(int id) {
        assert(0 <= id && id < BITS * WORDS);
        return words[id/BITS] & (1LL << (id%BITS));
    }
    void xorbit(int id) {
        assert(0 <= id && id < BITS * WORDS);
        words[id/BITS] ^= (1LL << (id%BITS));
    }
    string to_string(int strlen) {
        string s(strlen, '0');
        rep(i, strlen) if (getbit(i)) s[i] = '1';
        return s;
    }
    void normalize() {
        rep(i, WORDS) {
            if (words[i] < 0) {
                assert(i+1 < WORDS);
                words[i] += BASE;
                words[i+1]--;
            }
            assert(words[i] >= 0);
            ll carry = words[i] / BASE;
            words[i] %= BASE;
            if (carry) {
                assert(i+1 < WORDS);
                words[i+1] += carry;
            }
        }
    }
    bigint_t& operator^=(const bigint_t &o) {
        rep(i, WORDS) words[i] ^= o.words[i];
        return *this;
    }
    bigint_t& operator+=(int i) {
        words[0] += i; normalize();
        return *this;
    }
    bigint_t& operator-=(int i) {
        words[0] -= i; normalize();
        return *this;
    }
    bigint_t& operator*=(int i) {
        for (ll &a : words) a *= i;
        normalize();
        return *this;
    }
    int divrem(int o) {
        int rem = 0;
        for (int i = WORDS - 1; i >= 0; --i) {
            words[i] += rem * BASE;
            rem = int(words[i] % o);
            words[i] /= o;
        }
        normalize();
        return rem;
    }
};

char toPKN(int i) {
    if (i == 0) return 'P';
    if (i == 1) return 'N';
    if (i == 2) return 'K';
    assert(false);
}
int fromPKN(char ch) {
    if (ch == 'P') return 0;
    if (ch == 'N') return 1;
    if (ch == 'K') return 2;
    assert(false);
}
int gameValue(int a, int b) {
    int d = (a-b+3)%3;
    if (d == 0) return 0;
    if (d == 1) return 1;
    if (d == 2) return -1;
    assert(false);
}
int gameValue(bool iAmAlgosia, int mine, int other) {
    return iAmAlgosia ? gameValue(mine, other) : gameValue(other, mine);
}

// log(3,2) * 10**12
const ll LOG_3 = 1584962500721;
const ll LOG_2 = 1000000000000;
const ll LOG_4 = 2*LOG_2;
const ll LOG_4d3 = LOG_4 - LOG_3;

// const ll LOG_3 = 1;
// const ll LOG_2 = 1;
// const ll LOG_4 = 1;
// const ll LOG_4d3 = 1;

struct solver_t {
    bigint_t xorA, xorB;
    bigint_t myWord;
    int myWordLen;
    bool iAmAlgosia;

    int bal = 0;
    ll transmittedA = 0;
    ll transmittedB = 0;
    optional<int> lastProduced;
    vi otherOps;

    solver_t(string whoAmIStr, string myWordStr) {
        mt19937_64 gen(606133268284446439+2);
        xorA.fillrandom(gen);
        xorB.fillrandom(gen);
        myWord = bigint_t(myWordStr);
        myWordLen = sz(myWordStr);

        if (whoAmIStr == "Algosia") {
            iAmAlgosia = true;
            myWord ^= xorA;
        }
        else if (whoAmIStr == "Bajtek") {
            iAmAlgosia = false;
            myWord ^= xorB;
        }
        else assert(false);
    }

    ll& transmittedMine() { return iAmAlgosia ? transmittedA : transmittedB; }
    ll& transmittedOther() { return iAmAlgosia ? transmittedB : transmittedA; }
    int myScore() { return iAmAlgosia ? bal : -bal; }

    int produce() {
        assert(!lastProduced.has_value());

        if (bal == 0) {
            lastProduced.emplace(myWord.divrem(3));
        }
        else if (pair(transmittedMine(), iAmAlgosia) < pair(transmittedOther(), !iAmAlgosia)) {
            if (myWord.getbit(0) == 0 && myWord.getbit(1) == 0) {
                myWord.divrem(4);
                lastProduced.emplace(0);
            }
            else {
                int r = myWord.divrem(4);
                myWord *= 3;
                myWord += r - 1;
                if (myScore() == 1) lastProduced.emplace(2);
                else if (myScore() == -1) lastProduced.emplace(1);
                else assert(false);
            }
        }
        else {
            lastProduced.emplace(0);
        }

        return *lastProduced;
    }
    void consume(int other) {
        int mine = lastProduced.value();
        lastProduced.reset();

        if (bal == 0) {
            otherOps.pb(other);
            transmittedA += LOG_3;
            transmittedB += LOG_3;
        }
        else if (pair(transmittedMine(), iAmAlgosia) < pair(transmittedOther(), !iAmAlgosia)) {
            assert(other == 0);
            if (mine == 0)
                transmittedMine() += LOG_4;
            else
                transmittedMine() += LOG_4d3;
        }
        else {
            assert(mine == 0);
            if (other == 0) {
                transmittedOther() += LOG_4;
                otherOps.pb(3);
            }
            else {
                transmittedOther() += LOG_4d3;
                otherOps.pb(4);
            }
        }

        bal += gameValue(iAmAlgosia, mine, other);
        assert(abs(bal) <= 1);
    }

    string restore() {
        assert(myWord.iszero());

        bigint_t i;
        for (int op : otherOps | views::reverse) {
            if (op < 3) {
                i *= 3;
                i += op;
            }
            else if (op == 3) {
                i *= 4;
            }
            else if (op == 4) {
                int r = i.divrem(3);
                i *= 4;
                i += r + 1;
            }
            else assert(false);
        }
        i ^= iAmAlgosia ? xorB : xorA;

        return i.to_string(myWordLen);
    }
};

void check(string wa, string wb) {
    solver_t sa("Algosia", wa);
    solver_t sb("Bajtek", wb);

    int rounds = 1e9;

    rep(idround, 4999) {
        int ta = sa.produce();
        int tb = sb.produce();
        sa.consume(tb);
        sb.consume(ta);

        if (sa.myWord.iszero() && sb.myWord.iszero())
            rounds = min(rounds, idround + 1);
        // deb(_, sa.myWord.words[0], sa.myWord.words[1], sa.myWord.words[2]);
    }

    string geta = sa.restore();
    string getb = sb.restore();
    assert(geta == wb);
    assert(getb == wa);
    if (rounds > 4950)
        deb(rounds);
}

void check(int seed) {
    mt19937 rnd{(unsigned)seed};

    fwd(n, 1, 5001) {
        string sa(n, '0'), sb(n, '0');
        rep(i, n) {
            if (rnd() & 1) sa[i]++;
            if (rnd() & 1) sb[i]++;
        }
        check(sa, sb);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    // rep(i, 1e6) check(i);

    string whoami;
    int n, t;
    cin >> whoami >> n >> t;
    rep(_, t) {
        string word;
        cin >> word;
        solver_t solver(whoami, word);
        rep(__, 4999) {
            int i = solver.produce();
            char ch = toPKN(i);
            cout << ch << endl;
            cin >> ch;
            solver.consume(fromPKN(ch));
        }
        word = solver.restore();
        cout << "! " << word << endl;
    }

    cout << flush;
    _Exit(0);
}