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
#include <bits/stdc++.h>
using namespace std;
struct B{
    vector<int>d;
    B(){}
    B(int v){if(v)d.push_back(v);}
    bool z(){return d.empty();}
    void mul(int m,int a=0){
        long long c=a;
        for(int&x:d){long long u=x*1LL*m+c;x=u%1000000000;c=u/1000000000;}
        while(c){d.push_back(c%1000000000);c/=1000000000;}
    }
    int div(int m){
        long long r=0;
        for(int i=(int)d.size()-1;i>=0;--i){
            long long u=r*1000000000LL+d[i];d[i]=u/m;r=u%m;
        }
        while(d.size()&&!d.back())d.pop_back();
        return r;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string w;if(!(cin>>w))return 0;
    bool ia=(w=="Algosia");
    int n,t;cin>>n>>t;
    while(t--){
        string s;cin>>s;
        uint32_t sd=131337;
        string xs="";
        for(int i=0;i<n;++i){
            sd=sd*1664525+1013904223;
            xs+=(char)('0'+((sd>>16)&1));
        }
        for(int i=0;i<n;++i)s[i]=(s[i]-'0'^(xs[i]-'0'))+'0';
        s="1"+s;
        B X;for(char c:s)X.mul(2,c-'0');
        int D=0,cp=0;
        vector<pair<int,int>>h;
        for(int r=0;r<19900;++r){
            int so=0;
            if(D==0){if(!X.z())so=X.div(3);}
            else if((D==-1&&ia)||(D==1&&!ia)){
                if(!X.z()){
                    int c=X.div(4);
                    if(c<3){so=0;X.mul(3,c);}
                    else so=1;
                }
            }
            char mo='P';
            if(D==0)mo="PKN"[so];
            else if(D==1){if(ia)mo='P';else mo="NP"[so];}
            else{if(!ia)mo='P';else mo="NP"[so];}
            cout<<mo<<'\n';cout.flush();
            char mi;cin>>mi;
            int si=0;
            if(D==0){
                si=(mi=='P')?0:((mi=='K')?1:2);
                h.push_back({3,si});
            }else if(D==1){
                if(ia){si=(mi=='N')?0:1;h.push_back({4,si});}
            }else{
                if(!ia){si=(mi=='N')?0:1;h.push_back({4,si});}
            }
            if(mo=='P'&&mi=='P')cp++;else cp=0;
            if(mo!=mi){
                bool iw=(mo=='P'&&mi=='K')||(mo=='K'&&mi=='N')||(mo=='N'&&mi=='P');
                int df=iw?1:-1;
                if(!ia)df=-df;
                D+=df;
            }
            if(cp==40)break;
        }
        B Y;
        reverse(h.begin(),h.end());
        for(auto p:h){
            if(p.first==3)Y.mul(3,p.second);
            else{
                if(p.second==0){int c=Y.div(3);Y.mul(4,c);}
                else Y.mul(4,3);
            }
        }
        string bs="";
        while(!Y.z())bs+=to_string(Y.div(2));
        reverse(bs.begin(),bs.end());
        if(bs.length()>0)bs=bs.substr(1);
        string ans="";
        for(int i=0;i<n;++i){
            char b=(i<bs.length())?bs[i]:'0';
            ans+=(b-'0'^(xs[i]-'0'))+'0';
        }
        cout<<"! "<<ans<<'\n';cout.flush();
    }
    return 0;
}