1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;

namespace {

const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<19;
vector<char> tab = {'P', 'K', 'N'};
int rev[30];

int C(char a, char b)
{
    int x = rev[a - 'A'], y = rev[b - 'A'];
    if(x == y) return 0;
    if((x + 1) % 3 == y) return 1;
    return -1;
}

void Solve(int n, int r, int ttt)
{

    mt19937 rng(r + 20);
    string s, res;
    int pos = 0;

    cin >> s;
    for(int i = 0; i < n; ++i)
        if(rng() % 2 == 1)
            s[i] = (char)((int)s[i] ^ (int)'0' ^ (int)'1');

    int bal = 0;
    while(pos < n || (int)res.size() < n)
    {
        char a = 'P', b;
        if(pos < n && s[pos] == '1')
        {
            a = 'K';
            if(pos < n - 1 && s[pos + 1] == '1')
                a = 'N';
            ++pos;
        }
        ++pos;
        cout << a << "\n"; cout.flush();
        cin >> b;
        

        bal += C(a, b);
        if(r == 1)
            for(int i = 1; i <= 10000; ++i)
                {r += 1; r -= 1;}

        if(b == 'P')
            res.pb('0');
        if(b == 'K')
            {res.pb('1'); res.pb('0');}
        if(b == 'N')
            {res.pb('1'); res.pb('1');}

        if(!(pos < n || (int)res.size() < n)) break;
        while(bal != 0)
        {
            if(!(pos < n || (int)res.size() < n)) break;

            int xr = (pos + r <= (int)res.size());
            char c = 'P';
            if(xr == 1)
                c = tab[((int)(s[pos++] - '0') * bal + 3) % 3];
            cout << c << "\n"; cout.flush();
            char d;
            cin >> d;
            bal += C(c, d);

            // if(r == 1)
            //     cerr << "B: " << xr << " " << c << " " << d << "\n";
            // if(r == 0)
            //     cerr << "A: " << s[pos] << " " << xr << " " << c << " " << d << "\n"; 

            if(xr == 0)
                res.pb('0' + (int)(d != 'P'));
        }
    }
    while((int)res.size() > n)
        res.pop_back();
    mt19937 rng2((r^1)+20);
    for(int i = 0; i < n; ++i)
        if(rng2() % 2 == 1)
            res[i] = (char)((int)res[i] ^ (int)'0' ^ (int)'1');
    // if(r == 1)
    //     cerr << "Br: " << res << "\n";
    cout << "! " << res << "\n";
    cout.flush();
}

}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    rev['P' - 'A'] = 0; rev['K' - 'A'] = 1; rev['N' - 'A'] = 2;
    string g;
    cin >> g;
    int r = (int)(g[0] != 'A');
    int t, n; cin >> n >> t;
    while(t--)
        Solve(n, r, t);

    return 0;
}