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
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

string name;

void print(char c){
    cout << c;
    cout.flush();
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, t;
    cin >> name;
    cin >> n >> t;

    mt19937 gen(676767);

    string randomBits1;
    for(int i = 0; i < n; i++){
        randomBits1 += gen()%2 + '0';
    }
    string randomBits2;
    for(int i = 0; i < n; i++){
        randomBits2 += gen()%2 + '0';
    }

    auto xorS = [&](string & s, string &ra){
        for(int i = 0; i < n; i++){
            if(ra[i] == '1'){
                if(s[i] == '0') s[i] = '1';
                else s[i] = '0';
            }
        }
    };

    while(t--){
        string bits, other;
        cin >> bits;
        if(name == "Algosia")
            xorS(bits, randomBits1);
        else
            xorS(bits, randomBits2);

        bits += '1';
        int i = 0, j = 0;
        int balance = 0;
        while(i < n || j < n){
            char send, recieve;
            if(balance == 0){
                if(bits[i] == '0' && bits[i+1] == '0'){
                    send = 'P';
                    i+=2;
                }else if(bits[i] == '0' && bits[i+1] == '1'){
                    send = 'K';
                    i+=2;
                }else{
                    send = 'N';
                    i++;
                }
                print(send);

                cin >> recieve;

                if(recieve == 'P'){
                    other+="00";
                    j+=2;
                }else if(recieve == 'K'){
                    other+="01";
                    j+=2;
                }else{
                    other+="1";
                    j++;
                }
            }else if(j > i || (i == j && name == "Algosia")){
                if(balance == 1){
                    if(bits[i] == '0'){
                        send = 'P';
                    }else{
                        send = 'K';
                    }
                }else{
                    if(bits[i] == '0'){
                        send = 'P';
                    }else{
                        send = 'N';
                    }
                }
                i++;
                print(send);
                cin >> recieve;
            }else{
                send = 'P';
                print(send);
                cin >> recieve;

                if(recieve == 'P'){
                    other+='0';
                }else{
                    other+='1';
                }
                j++;
            }
            if(send == recieve) balance += 0;
            else if((send == 'P' && recieve == 'K') || (send == 'K' && recieve == 'N') || (send == 'N' && recieve == 'P'))
                balance += 1;
            else balance += -1;
            i = min(i, n);
            j = min(j, n);
        }
        if(name == "Algosia")
            xorS(other, randomBits2);
        else
            xorS(other, randomBits1);
        cout << "! " << other.substr(0, n);
        // cerr << name << " odopowiada "<<endl;
        cout.flush();
    }

    return 0;
}