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
#include "bits/stdc++.h"
using namespace std;

string code(string bits, int from, int to){
    vector <int> res = {0};
    for(char c : bits){
        int carry = c - '0';
        for(int i = res.size()-1; ~i; --i){
            int val = res[i] * from + carry;
            res[i] = val % to;
            carry = val / to;
        }
        while(carry){
            res.insert(res.begin(), carry % to);
            carry /= to;
        }
    }
    string ans = "";
    for(int x : res) ans += ('0' + x);
    return ans.empty() ? "0" : ans;
}

string encode(string x){
    return code("1" + x, 2, 3);
}

string decode(string x){
    return code(x, 3, 2).substr(1);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string name; cin >> name;
    int n, t; cin >> n >> t;
    for(;t--;){
        string bits2; cin >> bits2;
        string bits3 = encode(bits2);
        while(bits3.size() < 3160) bits3 = '0' + bits3;
        string ans = "";
        auto move = [](bool winner) -> void{
            cout << (winner ? "P\n" : "N\n");
            cout.flush();
        };
        for(int i = 0; i < bits3.size(); ++i){
            char my_move;
            if(bits3[i] == '0') {my_move = 'P'; cout << "P\n";}
            if(bits3[i] == '1') {my_move = 'K'; cout << "K\n";}
            if(bits3[i] == '2') {my_move = 'N'; cout << "N\n";}
            cout.flush();
            char other_move; cin >> other_move;
            if(other_move == 'P') ans += '0';
            if(other_move == 'K') ans += '1';
            if(other_move == 'N') ans += '2';
            if(my_move == other_move) continue;
            if(my_move == 'P' && other_move == 'K') move(1);
            if(my_move == 'P' && other_move == 'N') move(0);
            if(my_move == 'N' && other_move == 'P') move(1);
            if(my_move == 'N' && other_move == 'K') move(0);
            if(my_move == 'K' && other_move == 'N') move(1);
            if(my_move == 'K' && other_move == 'P') move(0);
            cin >> other_move;
        }       
        ans = decode(ans);
        cout << "! " << ans << '\n';
        cout.flush();
    }
}