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

using namespace std;

const string MASK_ALG = "00111011000111100001100000010111110101000101111001100101010101101001000101010011100000100011100011011110001101100001110010000001101001101001001011000100110100010100000101010000110000110011001110111001111111000110001001101010011110110000100101010001111110001110111100101110000001100000101100010111000110110001100110001101110000000110010111100010100101011001101110101101100010101110001000100000010001110001001110001010000101101010000111111000000110100110011100010101001111000110110111101001010100110101000111101001001100000000011100110110101001011100001010001001000101101100010110110000111000000010000111111010010110101100010000111010110101100000100010011101110110110001001110101011010110001001000111000111110011010011011011110101010000111100101110111001001110111111101111101010011000001011100101100100111010111000011111010001011110010010111010010110101010011000001000010101000110111010111010101110100011111111010010010110010110001010000111110010110011001010010011011111011010101001001011101000010100000101101000010100011000000011000011001111010000010100110000010010100010001011011001010110101011001111110000011010111011111111101011101011111110000100001001011110011011100011010001010001111001011110001101011101110000101101001010001101100010100111011011110100100001000000010101111100011110011101111111101001000001010111001110101000001000111101101001100000101111001010110100101111110000001100010101001010110111011111110110111000101101001000011011111101100101000101101101001101111100101100011010111010011000011010100101100001000001101100010011111111001011011011110100111001001111100101001011111110110010101101011000111101011001010110011000000101111011000000011111100100000101101010010000010001001011010000000011100001100101000001100101111010010111110110010111101100001111000001000001001000101011101100111011000010101111111010100110010111100011101110100101110011000001011011010001010101000011111011101101011101110111011011010101011100010111001111100100010010001101111010100101000111101010101010100100111101101011011101000010101010111100000010111100111101011101000001100100001110011110001000100001010100010110000111001010100111110001000101011110000111011011011000011000001110010110111101101000110000010011101000010110010010111001011101111111010110101000001111010111011001011100010011110111010001100101101111001010000100110101111101101011111101010011001010011000011000000100110111100110011001000010010001101101100110101111010111010001101010011111011101110100000110011001110010000100000000101010100100111100011100100111111111011111100111100100100100001000111001011101110011110010000000011001011001011011000010001110100010100111011110111001011100110000000101000100101001011001111000100000010100100101101111000110100110000110001101101010011000101010111101110111001000110000110011010001000101011000001001100110100011110101000011101010110010111010100011100000001000010000010101101101011100100101100110110001011100010110001111010101100100111001001001010000011000010111110000001111100110100011110000111100011111000000000110001001001001100101100010011100010100100111010011110011000110110001100111100000100111111000010001000001001101100110010100111001110111111010110100110111000111111001110000000011100101001100100100010100011011000011101000100001011100110011100011100011001001111011110000010111011001000011110000011001010101011111010111011111111110000011110110010110101100010100111100100001010100011010000100111101000101110000101100000010100110011010110001100110011011011101110010001110101001111101010111011001111000010011110110001010110010000101001100111000111001011100000111001110010011001101101011011001101011111101100101111100001001100110011001010110001111011100101010010110000110100111011110110100111000010110100101010101110010010111011010010011110111110010111111010010011110100011000000100111101000111101100001010010011111011110100101110011100000101110001001100101100110111110011111001101001101110100111111100111110101111000100011101001101001010100111111100000101011010000100011101001101100101101111111010101110011011100110110111010001100011001100000000111101111001011010011000010011111101010011101000101011110110101010011001000000111110100001110111010011011101010100110111001001110111001010011100001110100110000110111010001110111110111110001010111111001110001000011011100101000111000110001000111110000001010110100010010101111001001010011101000010011001011010000101000101011101011000011110001001101001011110000000101000101010110011101101110110111111111011001110100000101011011001000100010100110100010110000101101011101001100111011110010000011011101010111010010111010111100010110000001101111101001011111110011100010100111000001111011111101010010010000100101001000111100101111110110111111101010110101001010011100001110110100101010000100011101110111000110010010100000111011000101000001000010110011111000111110001011000001001001100001011000100100011110001110101111100001000101111111000001111010011101101100010110001001000111000111110000101101111110100010100000110101110110000010110110010001010010000100100010100111";

const string MASK_BAJ = "00110110100011011000110001001111001100100111100101000011011100101000000000010001101110100110001001000110100101100100110001000001011011111001100101111101000010111001111000111000001010111011010000010110111010000100101101011001000001011011010011011101101001001010111001100011010011111001100101101010011111111011011100100001000011011110110000110111111101001001100110100001001101110111110001010001011100100101110101010000110110111011110111101110111111001110010010010110110101001011001001110111000001101101101111001110110111010101110110111000110001110101110111000111100001111110110000011011001001110000100010011111101010110001101110010010000000111011000111010010101101101111001101101010100000000000110010111110010000101000111011000111000001010011110010101010011010100011011100101110010010110000010010000110100110100010101100100110000110110000100000001001110111101001000111001001010001101111010001100101100001100100000001001001100001101101010101110001100100011110001010100101011110101000001101011100011100100110000101001110011111011111101101111000001010111000110111100110101001100010110100001111101100001001000011110000101111000011001011100011110100010010101001101011000011101110011010010101010011010111101111110100110010100000111001101100101001010101111101101111110111011011001001011110011111011110100010110100001100101101011001100110110001001010011011110100000001011110001101111100001111110101100001011100111011101001101111100110100000011101101010100011110101001000110111101101111001110010011111111011110001110011101100011001010011110111000110111110111101011110110000001101101100111111000111101001111100001010100001100110111011100001000110011011010111001000011111011110001111111000110111111101110100111110100110110100100000111000010101101101001101111101110001011001111100000011011111111010001100101111101011100101000010111001000011100000100110011011110010010011010111110001010011100111100101111100011000110100010111110110111010001000101100100001001100000001101011101001100110000100110110010101110111000010111001111001001000000001010010000100000000010000010111101011000111100001110111111010110110100111001110010101110100100101100000000111001101000101011001010111111101111000110011000111111001001000101100110011001001111110011101100010011011000110111110000011010010000011101000101101011010010010100010111001010001101100101011001001010000000101110001001100100011100100101101101111101100101101110010010101001110100010001110000110010011110111100001110110010011001001011100001100110110110001111101100111111101001111000010010011101001100101110011000011111000010100010001010001101110110011111110000111100000101100101100011111000001110111001000010001110001000110011001110111101010011100110101010000110000101100001110111000111110110010101010100000111100001111000001101000010100110111101010011101111011001011100010110010011001010100000010000010101111111111001001010001001110101110100011001100001111111111101111001101000001001001010011001001100001010110000110101100111111111100110110000101011000011101111111000011000101011001011101100000100101011001100000101010111001010100000011100010000010110101010111100101101001010001011100001110001001111001111000000100100100010000100010011110100000100000001111011110000010100100100011110111001100000010100000100010111100010111100100100011111010001001001100101110000000000110101011100101011111101100011001000110011100010000111001010011101111001001100110000110001100011010100001111111100100110000111010000001011000000010110101000100110001101110111101011000110101000111111010110101101011111000001111101000110000011110010100001001100100110110111100111001100000101100111111000011110010011010101100111100100101001100010000110101001111010110011111111011001000011010001101110010111001110000100100111111101101101001101111100101110110010101100100001001001011000001010001111011011110111111110110111010000000000010001110110110011001011001001011000010110000100111100101110010010011110001111010010001011110010000011101001101111010101001110110110001110111001100010100001010011110100111101010101001111001010111011001000001100001101011000101101011101101000011100100011000110110111001111111000110000010101101101111001110000011111110011111111001001111010101110100111101110010110101001001110101111111010101100011110101111110111111000000101101110010000001100101000111110101000001111010011010111001101110110101000001010101111001101000000000101101000101101010011011101111001000110011001111001111111101001001011101101110010010010010000010001100010010100001000001100100111010010001011111000001001111100000100110000000110001100011111110000001110000111110001001000001110010100001010011000101100110101000100110110011000000101001101100110000010011100111001001111110011000010101100010001010010011110000110001100100111010111100011101111101100100101001010001000000101000111000111000101011001001000110110100011111001110011011011010111000011101101010100110001100011011001000101010111001000001111001010111000101101000110101000011011101000010010100100101010111001011100101010101001000011111001011100011011100011100";


string mask(const string& input, bool alg) {
	string output = "";
	
	for (int i = 0; i < input.size(); i++) {
		if ((alg && MASK_ALG[i] == '0') || (!alg && MASK_BAJ[i] == '0')) {
			output += input[i];
		} else {
			if (input[i] == '0') {
				output += '1';
			} else {
				output += '0';
			}
		}
	}
	
	return output;
}

enum Mode {
	TIE,
	ADV_P,
	ADV_NP
};

void algosia(bool alg) {
	string a;
	cin >> a;
	
	string s = mask(a, alg);	
	
	Mode mode = TIE;
	bool winner = false;
	bool lagging = false;
		
	string result = "";
	
	int i = 0;
	
	
	while (result.size() < s.size() || i < s.size() || mode != TIE) {
		switch(mode) {
			case TIE: {
				char pick;
				
				if (s[i] == '1') {
					pick = 'P';
					i += 1;
				} else {
					if (i == s.size() - 1 || s[i+1] == '0') {
						pick = 'K';
						i += 2;
					} else {
						pick = 'N';
						i += 2;
					}
				}
				
				cout << pick << "\n";
				cout.flush();
				
				char opp;
				
				cin >> opp;
				
				switch(opp) {
					case 'P': {
						result += "1";
						break;
					}
					case 'K': {
						if (result.size() == s.size() - 1) {
							result += "0";
						} else {
							result += "00";
						}
						break;
					}
					case 'N': {
						if (result.size() == s.size() - 1) {
							result += "0";
						} else {
							result += "01";
						}
						break;
					}
					default: break;
				}
				
				if (pick == 'P') {
					lagging = true;
					if (opp == 'N') {
						winner = false;
						mode = ADV_P;
					} else if (opp == 'K') {
						winner = true;
						mode = ADV_P;
					}
				} else if (pick == 'N') {
					lagging = false;
					if (opp == 'P') {
						winner = true;
						mode = ADV_P;
					} else if (opp == 'K') {
						winner = false;
						mode = ADV_NP;
					}
				} else if (pick == 'K') {
					lagging = false;
					if (opp == 'P') {
						winner = false;
						mode = ADV_P;
					} else if (opp == 'N') {
						winner = true;
						mode = ADV_NP;
					}
				}
				break;
			}
			
			case ADV_NP: {
				if (winner) {
					cout << "P\n";
				} else {
					cout << "N\n";
				}
				cout.flush();
				
				char opp;
				cin >> opp;
				
				mode = TIE;
				break;
			}
			
			case ADV_P: {
				char pick;
				
				if (lagging) {
					if (s[i] == '1') {
						pick = 'P';
					} else {
						pick = 'K';
					}
					i += 1;
				} else if (winner && !lagging) {
					pick = 'K';
				} else if (!winner && !lagging) {
					pick = 'P';
				}
				
				cout << pick << "\n";
				cout.flush();
				
				char opp;
				cin >> opp;
				
				if (!lagging) {
					if (opp == 'P') {
						result += "1";
					} else {
						result += "0";
					}
				}
				
				if (opp == pick) {
					mode = ADV_NP;
				} else if (opp != pick) {
					mode = TIE;
				}
				
				break;
			}
		
			default: break;
		}
	}
	
	
	
	cout << "! " << mask(result.substr(0, s.size()), !alg) << "\n";
	
	cout.flush();
}



int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
		
	string player;
	cin >> player;
	
	bool is_alg = (player == "Algosia");
	
	int n, t;
	cin >> n >> t;
	
	for (int i = 0; i < t; i++) {
		algosia(is_alg);
	}
}