#include <bits/stdc++.h>

using namespace std;
#define PB push_back
#define LL long long
//#define int LL
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define st first
#define nd second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define VI vector<int>
#define PII pair<int,int>
#define LD long double

template<class C> void mini(C& a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C& a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream &os, vector<T> V){
  os<<"[";for(auto vv:V)os<<vv<<",";return os<<"]";
} 

template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}


#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int NWORDS = 80; // 80 * 64 = 5120

struct BigNum {
    uint64_t w[NWORDS];
    BigNum() { memset(w, 0, sizeof(w)); }
};

int cmp(const BigNum &a, const BigNum &b) {
    FORD(i, NWORDS - 1, 0) {
        if (a.w[i] < b.w[i])
            return -1;
        if (a.w[i] > b.w[i])
            return 1;
    }
    return 0;
}

bool operator<(const BigNum &a, const BigNum &b) {
    return cmp(a, b) < 0;
}
bool operator<=(const BigNum &a, const BigNum &b) {
    return cmp(a, b) <= 0;
}
bool operator==(const BigNum &a, const BigNum &b) {
    return cmp(a, b) == 0;
}

void add(BigNum &a, const BigNum &b) {
    uint64_t carry = 0;
    REP(i, NWORDS) {
        __uint128_t s = (__uint128_t)a.w[i] + b.w[i] + carry;
        a.w[i] = (uint64_t)s;
        carry = (uint64_t)(s >> 64);
    }
}

void sub(BigNum &a, const BigNum &b) {
    uint64_t borrow = 0;
    REP(i, NWORDS) {
        __uint128_t s = (__uint128_t)a.w[i] - b.w[i] - borrow;
        a.w[i] = (uint64_t)s;
        borrow = (s >> 64) ? 1 : 0;
    }
}

uint64_t divmod(BigNum &a, uint64_t d) {
    __uint128_t rem = 0;
    FORD(i, NWORDS - 1, 0) {
        rem = (rem << 64) | a.w[i];
        a.w[i] = (uint64_t)(rem / d);
        rem = rem % d;
    }
    return (uint64_t)rem;
}

void mulsmall(BigNum &a, uint64_t d) {
    __uint128_t carry = 0;
    REP(i, NWORDS) {
        carry += (__uint128_t)a.w[i] * d;
        a.w[i] = (uint64_t)carry;
        carry >>= 64;
    }
}

void shr(BigNum &a, int s) {
    REP(i, NWORDS - 1) {
        a.w[i] = (a.w[i] >> s) | (a.w[i + 1] << (64 - s));
    }
    a.w[NWORDS - 1] >>= s;
}

void setbit(BigNum &a, int k) {
    a.w[k / 64] |= (1ULL << (k % 64));
}

int getbit(const BigNum &a, int k) {
    return (a.w[k / 64] >> (k % 64)) & 1;
}

BigNum from_bits(const string &s) {
    BigNum r;
    int n = s.size();
    REP(i, n) {
        if (s[i] == '1') {
            setbit(r, n - 1 - i);
        }
    }
    return r;
}

string to_bits(const BigNum &a, int n) {
    string s(n, '0');
    REP(i, n) {
        if (getbit(a, n - 1 - i))
            s[i] = '1';
    }
    return s;
}

//xorshift64
struct Rng {
    uint64_t s;
    Rng(uint64_t seed) : s(seed) {}
    uint64_t next() {
        s ^= s << 13;
        s ^= s >> 7;
        s ^= s << 17;
        return s;
    }
};

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

    string role;
    cin >> role;
    bool is_algosia = (role == "Algosia");

    int n, t;
    cin >> n >> t;
    uint64_t seed = 213742997ULL;

    Rng rng(seed);
    vector<int> mask(n);
    REP(i, n) {
        mask[i] = rng.next() & 1;
    }

    auto is_determined = [](const BigNum &lo, const BigNum &hi) -> bool {
        BigNum diff = hi;
        sub(diff, lo);
        if (diff.w[0] > 1)
            return false;
        for (int i = 1; i < NWORDS; i++) {
            if (diff.w[i] != 0)
                return false;
        }
        return true;
    };

    for (int tc = 0; tc < t; tc++) {
        string my_str;
        cin >> my_str;

        // Apply mask
        string masked_str = my_str;
        REP(i, n) {
            masked_str[i] = ((my_str[i] - '0') ^ mask[i]) + '0';
        }

        BigNum my_num = from_bits(masked_str);

        BigNum max_val;
        setbit(max_val, n);

        BigNum my_l, my_r = max_val;
        BigNum their_l, their_r = max_val;

        int score = 0; // algosia - bajtek

        auto split_thirds = [](const BigNum &lo, const BigNum &hi, BigNum &b1, BigNum &b2) {
            BigNum range = hi;
            sub(range, lo);
            BigNum third = range;
            divmod(third, 3);
            
            bool is_zero = true;
            REP(i, NWORDS) {
                if (third.w[i] != 0) {
                    is_zero = false; 
                    break;
                }
            }
            if (is_zero)
                third.w[0] = 1;
            b1 = lo;
            add(b1, third);
            b2 = b1;
            add(b2, third);
        };

        auto which_third = [](const BigNum &val, const BigNum &lo, const BigNum &b1, const BigNum &b2) -> int {
            if (cmp(val, b1) < 0)
                return 0;
            if (cmp(val, b2) < 0)
                return 1;
            return 2;
        };

        auto apply_third = [](int choice, BigNum &lo, BigNum &hi, const BigNum &b1, const BigNum &b2) {
            if (choice == 0) {
                hi = b1;
            } else if (choice == 1) {
                lo = b1;
                hi = b2;
            } else {
                lo = b2;
            }
        };

        auto split_at_quarter = [](const BigNum &lo, const BigNum &hi) -> BigNum {
            BigNum range = hi;
            sub(range, lo);
            BigNum quarter = range;
            shr(quarter, 2);
            bool is_zero = true;
            REP(i, NWORDS) {
                if (quarter.w[i] != 0) {
                    is_zero = false;
                    break;
                }
            }
            if (is_zero)
                quarter.w[0] = 1;
            BigNum sp = lo;
            add(sp, quarter);
            return sp;
        };

        while (!(is_determined(my_l, my_r) && is_determined(their_l, their_r))) {
            char my_move, their_move;

            if (score == 0) {
                // triple_split
                BigNum my_b1, my_b2;
                split_thirds(my_l, my_r, my_b1, my_b2);
                int my_choice = which_third(my_num, my_l, my_b1, my_b2);

                const char symbols[] = "PKN";
                my_move = symbols[my_choice];

                cout << my_move << '\n';
                cout.flush();
                cin >> their_move;

                int their_choice;
                if (their_move == 'P')
                    their_choice = 0;
                else if (their_move == 'K')
                    their_choice = 1;
                else
                    their_choice = 2;

                apply_third(my_choice, my_l, my_r, my_b1, my_b2);

                BigNum their_b1, their_b2;
                split_thirds(their_l, their_r, their_b1, their_b2);
                apply_third(their_choice, their_l, their_r, their_b1, their_b2);

                if (my_move != their_move) {
                    if ((my_move == 'P' && their_move == 'K') || (my_move == 'K' && their_move == 'N') || (my_move == 'N' && their_move == 'P'))
                        score += (is_algosia ? 1 : -1);
                    else
                        score += (is_algosia ? -1 : 1);
                }
            } else {
                // score != 0.
                // less transmitted -> K.
                // equal: Algosia -> K.
                BigNum alg_r, baj_r;
                if (is_algosia) {
                    alg_r = my_r;
                    sub(alg_r, my_l);
                    baj_r = their_r;
                    sub(baj_r, their_l);
                } else {
                    baj_r = my_r;
                    sub(baj_r, my_l);
                    alg_r = their_r;
                    sub(alg_r, their_l);
                }
                bool alg_plays_rock = (cmp(alg_r, baj_r) <= 0);
                bool i_play_rock = (is_algosia == alg_plays_rock);
                bool i_am_ahead = (is_algosia && score > 0) || (!is_algosia && score < 0);

                if (i_play_rock) {
                    my_move = 'K';
                    cout << my_move << '\n';
                    cout.flush();
                    cin >> their_move;

                    bool they_are_ahead = !i_am_ahead;
                    BigNum sp = split_at_quarter(their_l, their_r);

                    if (they_are_ahead) {
                        // they: K=lower(draw), N=upper(they lose)
                        if (their_move == 'K') {
                            their_r = sp;
                        } else {
                            their_l = sp;
                            if (is_algosia)
                                score++;
                            else
                                score--;
                        }
                    } else {
                        // they: K=lower(draw), P=upper(they win)
                        if (their_move == 'K') {
                            their_r = sp;
                        } else {
                            their_l = sp;
                            if (is_algosia)
                                score--;
                            else
                                score++;
                        }
                    }
                } else {
                    BigNum sp = split_at_quarter(my_l, my_r);

                    if (cmp(my_num, sp) < 0) {
                        my_move = 'K';
                        my_r = sp;
                    } else {
                        my_move = i_am_ahead ? 'N' : 'P';
                        my_l = sp;
                    }

                    cout << my_move << '\n';
                    cout.flush();
                    cin >> their_move;

                    if (my_move == 'N') {
                        if (is_algosia)
                            score--;
                        else
                            score++;
                    } else if (my_move == 'P') {
                        if (is_algosia)
                            score++;
                        else
                            score--;
                    }
                }
            }
        }

        string their_masked_str = to_bits(their_l, n);
        string their_str(n, '0');
        REP(i, n) {
            their_str[i] = ((their_masked_str[i] - '0') ^ mask[i]) + '0';
        }
        cout << "! " << their_str << '\n';
        cout.flush();
    }
    return 0;
}