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
#include <bits/stdc++.h>
#include <cstdlib>
#include <random>
using namespace std;
using ind = long long;
using cind = const ind;
#define FOR(i,l,r) for(ind i = (l); i <= (r); i++)
#define FORD(i,l,r) for(ind i = (l); i >= (r); i--)
#define DEBUG_ON false
#define debug if constexpr(DEBUG_ON)
#define err debug cerr

string person;
ind N,T;
mt19937_64 rng_core(85021);
ind common_key[50'001];
ind bajtosia_key[50'001];
ind rand_seqence[50'001];
ind send_id=0;

ind my_bits[5'001];
ind his_bits[5'001];
ind balance=0;

char send_char(char c){
    cout << c << endl;
    cin >> c;
    return c;
}
ind send_tri(ind tri){
    tri = (tri + rand_seqence[send_id]) % 3;
    ind tri_orig = tri;
    char returned;
    if(tri==0) returned = send_char('P');
    if(tri==1) returned = send_char('K');
    if(tri==2) returned = send_char('N');
    if(returned == 'P') tri = 0;
    if(returned == 'K') tri = 1;
    if(returned == 'N') tri = 2;
    ind tri_ret = tri;
    tri = (tri - rand_seqence[send_id] + 3) % 3;
    if(tri_orig == ((tri_ret+1)%3)) balance=-1;
    if(tri_ret == ((tri_orig+1)%3)) balance=1;
    return tri;
}
void solve(){
    string s;
    cin >> s;
    FOR(i,1,s.size()) my_bits[i] = s[i-1] - '0';
    FOR(i,1,s.size()) my_bits[i] = (my_bits[i] + common_key[i])%2;
    if(person != "Bajtek") FOR(i,1,s.size()) my_bits[i] = (my_bits[i] + bajtosia_key[i])%2;
    FOR(i,1,s.size()) his_bits[i] = 0;

    ind my_bit_to_send_id=1;
    ind his_bit_to_send_id=1;

    while(true){
        if(my_bit_to_send_id > N and his_bit_to_send_id > N) break;
        ind returned = 0;
        if(balance != 0){
            if(balance==1) send_tri(1);
            else send_tri(0);
            continue;
        }
        if(my_bit_to_send_id <= N){
            ind b1;
            b1 = my_bits[my_bit_to_send_id];
            my_bit_to_send_id++;
            if(b1 == 1){
                returned = send_tri(2);
            }else{
                ind b2 = 0;
                if(my_bit_to_send_id <= N) b2 = my_bits[my_bit_to_send_id];
                my_bit_to_send_id++;
                returned = send_tri(b2);
            }
        }else{
            returned = send_tri(rng_core()%3);
        }
        if(his_bit_to_send_id <= N){
            if(returned == 2){
                his_bits[his_bit_to_send_id] = 1;
                his_bit_to_send_id++;
            }else{
                his_bits[his_bit_to_send_id] = 0;
                his_bit_to_send_id++;
                if(his_bit_to_send_id <= N){
                    his_bits[his_bit_to_send_id] = returned;
                    his_bit_to_send_id++;
                }
            }
        }
        
        
    }

    
    FOR(i,1,s.size()) his_bits[i] = (his_bits[i] + common_key[i])%2;
    if(person != "Algosia") FOR(i,1,s.size()) his_bits[i] = (his_bits[i] + bajtosia_key[i])%2;
    FOR(i,1,s.size()) s[i-1] = char(his_bits[i]) + '0';
    cout << "! " << s << endl;
}
int main(){
    cin >> person >> N >> T;
    FOR(i,0,50000) rand_seqence[i] = rng_core()%3;
    FOR(i,0,50000) common_key[i] = rng_core()%3;
    FOR(i,0,50000) bajtosia_key[i] = rng_core()%3;
    FOR(i,1,T) solve();
}