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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <bits/stdc++.h>
#define B (1<<29)
char s[5009],ss[3]={'P','K','N'},tt[3];
int op,N,T,v[5009],v2[5009],v3[5009],b[5009],dp[1100][280][31],bs[31],v4[5009],
v5[5009],v6[5009],c[5009],ccc,vx[5009];
inline int cz(int x) {
    //if(op==1) std::cerr<<op<<' '<<x<<'\n';
    printf("%c\n",ss[x]);
    fflush(stdout);
    scanf("%s",tt);
    int as=0;
    if(tt[0]==ss[0]) as=0;
    if(tt[0]==ss[1]) as=1;
    if(tt[0]==ss[2]) as=2;
    if(as==(x+1)%3) ccc++;
    else if(as==(x+2)%3) ccc--;
    assert(-1<=ccc&&ccc<=1);
    return as;
}
signed main(void) {
    scanf("%s",s+1);
    if(s[1]=='A') op=1;else op=2;
    scanf("%d %d",&N,&T);
    std::mt19937 rng((op+6)*19530615);
    std::mt19937 rng2((9-op)*19530615);
    for(int i=0;i<5000;i++) {
        v[i]=rng()%2;
        vx[i]=rng2()%2;
    }

    for(int i=0;i<=1088;i++) {
        dp[i][0][0]=1;
        for(int j=1;j<=i&&j<=272;j++) {
            for(int k=0;k<=30;k++) {
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k];
            }
            for(int k=0;k<=30;k++) {
                if(dp[i][j][k]>=B) {
//                  assert(k<30);
                    dp[i][j][k]-=B;
                    dp[i][j][k+1]++;
                }
            }
        }
    }
    int cx=0;
    while(T--) {
        cx++;
    //  if(op==1) std::cerr<<cx<<std::endl;
        ccc=0;
        scanf("%s",s+1);
//      for(int i=1;i<=N;i++) s[i]=rng()%2+'0';
        memset(v2,0,sizeof(v2));
        for(int i=1;i<=N;i++) {
            v2[i-1]=s[i]-'0';
        }
        for(int i=0;i<5000;i++) {
            v2[i]^=v[i];
        }
        for(int i=0;i<2602;i++) {
            int as=0;
            for(int j=4999;j>=0;j--) {
                as=(2*as+v2[j])%3;
            }
            b[i]=as;
            for(int j=4999;j>=0;j--) {
                int aq=0;
                for(int k=j;k<=j+3&&k<5000;k++) {
                    if(v2[k]) aq+=(1<<k-j);
                }
                if(aq>=3) {
                    v3[j]=1;
                    v2[j]-=3;
                } else {
                    v3[j]=0;
                }
                int p=j;
                while(p<5000&&v2[p]<0) {
                    while(v2[p]<0) {
                        v2[p]+=2;
                        v2[p+1]--;
                    }
                    p++;
                }
            }
            for(int j=0;j<=4999;j++) {
                v2[j]=v3[j];
            }
        }
        memset(bs,0,sizeof(bs));
        for(int j=0;j<888;j++) {
            if(v2[j]) {
                bs[j/29]+=(1<<(j%29));
            }
        }
        int cur=0,fq=0;
//      for(int k=30;k>=0;k--) {
//          if(bs[k]!=dp[1088][272][k]) {
//              if(op==1) assert(bs[k]<dp[1088][272][k]);
///             fq=1;
//              break;
//          }
//      }
//      if(op==1) assert(fq);
//      if(op==1) {
//          for(int k=30;k>=0;k--) {
//              std::cerr<<bs[k]<<' ';
//          }
//          std::cerr<<'\n';
//          for(int k=30;k>=0;k--) {
//              std::cerr<<dp[1088][272][k]<<' ';
//          }
//          std::cerr<<'\n';
//      }
        for(int j=1087;j>=0;j--) {
            //xuan 1
            //check j,272-cur-1
            bool gg=0;
            for(int k=30;k>=0;k--) {
                if(bs[k]!=dp[j][272-cur][k]) {
                    if(bs[k]<dp[j][272-cur][k]) {
                        gg=1;
                        break;
                    }
                    break;
                }
            }
//          if(op==1) std::cerr<<gg<<std::endl;
            v4[j]=0;
            if(gg) continue;
            v4[j]=1;
            for(int k=30;k>=0;k--) bs[k]-=dp[j][272-cur][k];
            for(int k=0;k<=30;k++) {
                if(bs[k]<0) {
                    assert(k<30);
                    bs[k]+=B;
                    bs[k+1]--;
                }
            }
            cur++;
        //  if(cur==272) break;
        }
        assert(cur==272);
        if(op==1) for(int k=0;k<=30;k++) assert(bs[k]==0);
//      for(int i=1088;i<5000;i++) if(rng()%4) v4[i]=0;else v4[i]=1;
        int p1=0,p2=0,p3=0,fl=0,cs=0;
        while(p1<2602||p2<1088||p3<1088) {
            if(p1<2602) {
                int a=cz(b[p1]);
                c[p1]=a;
                p1++;
            } else {
                int a=cz(v4[p2]);
                v6[p3]=a;
                p2++;p3++;
            }
            while(ccc) {
                if(p2==1088&&p3==1088) {
                    if(ccc>0) {
                        cz(1);
                    } else {
                        cz(0);                          
                    }
                    assert(ccc==0);
                    break;
                }
                if(fl+1==op) {
                    if(v4[p2]==1) {
                        cz(0);
                    } else if(ccc>0) {
                        cz(1);
                    } else {
                        cz(2);
                    }
                    p2++;
                } else {
                    if(cz(0)) v6[p3]=0;
                    else v6[p3]=1;
                    p3++;
                }
                fl^=1;
            }
        }
        cur=0;
        for(int j=0;j<=30;j++) bs[j]=0;
        for(int j=1087;j>=0;j--) {
            if(v6[j]==0) continue;
            for(int k=0;k<=30;k++) {
                bs[k]+=dp[j][272-cur][k];
            }
            for(int k=0;k<=30;k++) {
                if(bs[k]>=B) {
                    assert(k<30);
                    bs[k]-=B;
                    bs[k+1]++;
                }
            }
            cur++;
        }
        memset(v2,0,sizeof(v2));
        for(int k=0;k<=30;k++) {
            for(int l=0;l<=28;l++) {
                if((bs[k]>>l)&1) {
                    v2[29*k+l]=1;
                }
            }
        }
        for(int j=2601;j>=0;j--) {
            for(int k=0;k<5000;k++) {
                v2[k]*=3;
            }
            v2[0]+=c[j];
            for(int k=0;k<5000;k++) {
                int bb=v2[k]/2;
                v2[k]-=2*bb;
                v2[k+1]+=bb;
            }
        }
        for(int k=0;k<5000;k++) v2[k]^=vx[k];
        printf("! ");
        for(int k=0;k<N;k++) {
            printf("%d",v2[k]);
        }
        printf("\n");
        fflush(stdout);
    }
}