#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
 
// hloya template v26
 
// ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
// ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
// ░░░░░░█░█░▀░░░░░▀░░▀░░░░█░█░░░░░
// ░░░░░░█░█░░░░░░░░▄▀▀▄░▀░█░█▄▀▀▄░
// █▀▀█▄░█░█░░▀░░░░░█░░░▀▄▄█▄▀░░░█░
// ▀▄▄░▀██░█▄░▀░░░▄▄▀░░░░░░░░░░░░▀▄
// ░░▀█▄▄█░█░░░░▄░░█░░░▄█░░░▄░▄█░░█
// ░░░░░▀█░▀▄▀░░░░░█░██░▄░░▄░░▄░███
// ░░░░░▄█▄░░▀▀▀▀▀▀▀▀▄░░▀▀▀▀▀▀▀░▄▀░
// ░░░░█░░▄█▀█▀▀█▀▀▀▀▀▀█▀▀█▀█▀▀█░░░
// ░░░░▀▀▀▀░░▀▀▀░░░░░░░░▀▀▀░░▀▀░░░░
 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
// #include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <optional>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
//#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#include <unistd.h>


using namespace std;
 
bool dbg = 0;
  
clock_t start_time = clock();
#define current_time fixed<<setprecision(6)<<(ld)(clock()-start_time)/CLOCKS_PER_SEC
  
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define sqr(x) ((x) * (x))
 
#define ull unsigned long long
#define ll long long
#define ld long double
#define pii pair<int,int>
#define umap unordered_map<int, int>
 
#define files1 freopen("input.txt","r",stdin)
#define files2 freopen("output.txt","w",stdout)
#define files files1;files2
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0)
 
// #define endl '\n'
#define ln(i,n) " \n"[(i) == (n) - 1]
 
void bad(string mes = "Impossible"){cout << mes;exit(0);}
void bad(int mes){cout << mes;exit(0);}
 
template<typename T>
string bin(T x, int st = 2){
    string ans = "";
    while (x > 0){
        ans += char('0' + x % st);
        x /= st;
    }
    reverse(ans.begin(), ans.end());
    return ans.empty() ? "0" : ans;
}
 
mt19937_64 mt_rand(
    chrono::system_clock::now().time_since_epoch().count()
);
 
template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }
 
// inline int popcount(int x){
//     int count = 0;
//     __asm__ volatile("POPCNT %1, %0;":"=r"(count):"r"(x):);
//     return count;
// }
  
template<typename T>
T input(){
    T ans = 0, m = 1;
    char c = ' ';
  
    while (!((c >= '0' && c <= '9') || c == '-')) {
        c = getchar();
    }
  
    if (c == '-')
        m = -1, c = getchar();
    while (c >= '0' && c <= '9'){
        ans = ans * 10 + (c - '0'), c = getchar();
    }
    return ans * m;
}
 
template<typename T>
T gcd (T a, T b) { while (b) { a %= b; swap (a, b); } return a; }
  
template<typename T> void read(T& a) { a = input<T>(); }
template<typename T> void read(T& a, T& b) { read(a), read(b); }
template<typename T> void read(T& a, T& b, T& c) { read(a, b), read(c); }
template<typename T> void read(T& a, T& b, T& c, T& d) { read(a, b), read(c, d); }
 
const int inf = 1e9 + 20;
const short short_inf = 3e4 + 20;
const long double eps = 1e-12;
const int maxn = (int)5e5 + 3, base = 998244353;
const ll llinf = 2e18 + 5;
const int mod = 1e9 + 7;
 
int binpow(int a, int s) { 
    int res = 1;
    while (s) {
        if (s % 2) {
            res = 1ll * res * a % base;
        }
        a = 1ll * a * a % base;
        s /= 2;
    }
    return res;
}

vector<int> conv(const vector<int>& d, bool tobin, int len2, int len3) {
    if (tobin) {
        vector<int> res(len2, 0);
        for (int i = 0; i < len3; ++i) {
            int carry = d[i];
            for (int j = 0; j < len2; ++j) {
                int val = res[j] * 3 + carry;
                res[j] = val % 2;
                carry = val / 2;
            }
        }
        reverse(all(res));
        return res;
    } else {
        vector<int> res(len3, 0);
        for (int i = 0; i < len2; ++i) {
            int carry = d[i];
            for (int j = 0; j < len3; ++j) {
                int val = res[j] * 2 + carry;
                if (val >= 3) {
                    res[j] = val - 3;
                    carry = 1;
                } else {
                    res[j] = val;
                    carry = 0;
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
}

string items = "PKN";
int req = 0, worst = 0;

int ddd = 2;

const int N = 1; // FULL, N=0, N=9

vector<int> brutesolve(int pers, vector<int> d, int delta = 0) {
    int len2 = d.size();
    int len3 = ceil(1. * len2 * log(2) / log(3));

    vector<int> c3 = conv(d, false, len2, len3);
    assert(c3.size() == len3);

    vector<int> opp3;
    
    int ptr = 0;
    string c;

    while (ptr < c3.size()) {
        ++req;
        if (delta > 0) {
            cout << "N" << endl;
            cin >> c;
            assert(c == "K");
            delta = 0;
            continue;
        }
        if (delta < 0) {
            cout << "K" << endl;
            cin >> c;
            assert(c == "N");
            delta = 0;
            continue;
        }

        int myitem = c3[ptr];

        cout << items[myitem] << endl;
        cin >> c;
        int oppitem;
        if (c == "P") oppitem = 0;
        if (c == "K") oppitem = 1;
        if (c == "N") oppitem = 2;

        opp3.pb(oppitem);
        ++ptr;
        
        if (myitem == oppitem) {
            continue;
        }
        if ((myitem + 1) % 3 == oppitem) {
            delta = 1;
        } else {
            delta = -1;
        }
    }
    assert(opp3.size() == len3);

    auto ans = conv(opp3, true, len2, len3);
    return ans;
}

vector<int> solve(int pers, vector<int> d, int delta = 0) {
    if (d.size() <= N) {
        return brutesolve(pers, d, delta);
    }
    int len2 = d.size();
    int len3 = ceil(1. * len2 * log(2) / log(3));

    vector<int> c3 = conv(d, false, len2, len3);

    assert(c3.size() == len3);

    vector<int> opp3(len3, -1);

    int ptr = 0;
    int back_my = 0;
    int back_opp = 0;

    string c;
    
    // Where not set K
    vector<int> idxmy, idxopp;

    while (ptr + max(back_my, back_opp) < c3.size()) {
        ++req;
        if (delta != 0) {
            // if (idxmy.size() < idxopp.size() || (pers == 0 && idxmy.size() == idxopp.size())) {
            if (back_my < back_opp || (pers == 0 && back_my == back_opp)) {
                if (c3[len3 - back_my - 1] == 1) {
                    // just k
                    cout << "K" << endl;
                    back_my++;
                    cin >> c;
                    assert(c == "K");
                } else {
                    cout << ((delta > 0) ? "N" : "P") << endl;
                    cin >> c;
                    assert(c == "K");
                    idxmy.pb(back_my);
                    back_my++;
                    delta = 0; // not k
                }
            } else {
                cout << "K" << endl;
                cin >> c;
                if (c == "K") {
                    opp3[len3 - back_opp - 1] = 1;
                    back_opp++;
                } else {
                    assert((delta > 0 && c == "P") || (delta < 0 && c == "N"));
                    idxopp.pb(back_opp);
                    back_opp++;
                    delta = 0;
                }
            }
            continue;
        }
        int myitem = c3[ptr];

        cout << items[myitem] << endl;
        cin >> c;
        int oppitem;
        if (c == "P") oppitem = 0;
        if (c == "K") oppitem = 1;
        if (c == "N") oppitem = 2;

        opp3[ptr] = oppitem;
        ++ptr;
        
        if (myitem == oppitem) {
            continue;
        }
        if ((myitem + 1) % 3 == oppitem) {
            delta = 1;
        } else {
            delta = -1;
        }
    }
    if (back_my != back_opp) {
        // stupid option

        if (delta > 0) {
            ++req;
            cout << "N" << endl;
            cin >> c;
            assert(c == "K");
            delta = 0;
        }
        if (delta < 0) {
            ++req;
            cout << "K" << endl;
            cin >> c;
            assert(c == "N");
            delta = 0;
        }

        if (back_my < back_opp) {
            ++req;
            // Just giving my item and upd delta for recursion
            int myitem = c3[ptr];
            cout << items[myitem] << endl;
            cin >> c;
            
            int oppitem;
            if (c == "P") oppitem = 0;
            if (c == "K") oppitem = 1;
            if (c == "N") oppitem = 2;
            
            if (myitem == oppitem) {
                delta = 0;
            } else if ((myitem + 1) % 3 == oppitem) {
                delta = 1;
            } else {
                delta = -1;
            }

            back_my++;
        } else {
            ++req;
            int myitem = 1; // Just K why not
            cout << items[myitem] << endl;
            cin >> c;
            
            int oppitem;
            if (c == "P") oppitem = 0;
            if (c == "K") oppitem = 1;
            if (c == "N") oppitem = 2;

            opp3[ptr] = oppitem;
            
            if (myitem == oppitem) {
                delta = 0;
            } else if ((myitem + 1) % 3 == oppitem) {
                delta = 1;
            } else {
                delta = -1;
            }

            back_opp++;
        }
    }
    assert(back_opp == back_my && ptr + back_opp == len3);

    vector<int> newd;
    for (auto i : idxmy) {
        assert(c3[len3 - i - 1] != 1);
        newd.pb(c3[len3 - i - 1] == 0);
    }

    // idxmy size != idxopp size
    // We add 0
    // Opp doesnt, just ignores it
    while (idxmy.size() < idxopp.size()) {
        newd.pb(0); // aligment
        idxmy.pb(-1); // just to for
    }

    int totsize = max(idxmy.size(), idxopp.size());

    vector<int> rec_ans;
    if (totsize != 0) {
        rec_ans = solve(pers, newd, delta);
    }

    for (int i = 0; i < idxopp.size(); ++i) {
        opp3[len3 - 1 - idxopp[i]] = rec_ans[i] ? 0 : 2;
    }
    // fill the rest of opp3
    auto ans = conv(opp3, true, len2, len3);
    return ans;
}


int main() {
    // files1;
    // fast_io;
    string name;
    cin >> name;
    int pers = (name != "Algosia");

    // TODO if too small (<N) just stupid algo

    int t, n;
    cin >> n >> t;

    mt19937_64 mt_rand_a(
        573495378
    );
    mt19937_64 mt_rand_b(
        789111420
    );

    vector<int> mask_a(n), mask_b(n);
    for (int i = 0; i < n; ++i) {
        mask_a[i] = mt_rand_a() % 2;
    }
    for (int i = 0; i < n; ++i) {
        mask_b[i] = mt_rand_b() % 2;
    }

    int x = 0;
    while (t--) {
        req = 0;
        int testid = x++;
        if (pers == 0) {
            // cerr << "TEST: " << testid << endl;
        }
        string rawstr;
        cin >> rawstr;

        assert(rawstr.size() == n);
        
        vector<int> d;
        for (int i = 0; i < n; ++i) {
            d.pb(rawstr[i] - '0');
            d[i] ^= (pers == 0 ? mask_a[i] : mask_b[i]);
        }

        auto res = solve(pers, d);
        for (int i = 0; i < n; ++i) {
            res[i] ^= (pers == 0 ? mask_b[i] : mask_a[i]);
        }
        cout << "! ";
        for (int i = 0; i < n; ++i) {
            cout << res[i];
        }
        cout << endl;
    }
    return 0;
}