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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

constexpr size_t MAXT = 10;
constexpr size_t MAXN = 1e4;

size_t my_swaps[2][MAXT][MAXN];
bool my_bitmask[2][MAXT][MAXN];

void build_rands() {
    std::mt19937 gen(483923);
    std::uniform_int_distribution<int> uni_d;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < MAXT; j++) {
            for (int k = 0; k < MAXN; k++) {
                my_swaps[i][j][k] = uni_d(gen, std::uniform_int_distribution<int>::param_type{0, k});
                if (my_swaps[i][j][k] > k) {
                    std::cout << "BIG PROBLEM!!\n";
                }
                my_bitmask[i][j][k] = uni_d(gen, std::uniform_int_distribution<int>::param_type{0,1});
            }
        }
    }
}

// returns vector of length divisible by 20
std::vector<int64_t> encode_string(std::string s, bool is_algosia, size_t test_id) {
    test_id = test_id % MAXT;
    while (s.size() % 20 != 0) {
        s+='0';
    }
    for (size_t i = 0; i < s.size(); i++) {
        std::swap(s[i], s[my_swaps[is_algosia][test_id][i]]);
    }
    std::vector<bool> xored_str;
    for (size_t i = 0; i < s.size(); i++) {
        bool str_v = (s[i] == '1');
        xored_str.push_back(str_v ^ my_bitmask[is_algosia][test_id][i]);
    }


    std::vector<bool> my_bools;
    std::vector<int64_t> result;
    for (size_t i = 0; i < s.size(); i++) {
        my_bools.push_back(xored_str[i]);
        if (my_bools.size() == 20) {
            int64_t val_to_push = 0;
            for (size_t j = 0; j < 20; j++) {
                if (my_bools[j]) {
                    val_to_push = (1 << j) | val_to_push;
                }
            }
            result.push_back(val_to_push);
            my_bools.clear();
        }
    }
    return result;
}

std::string decode_string(std::vector<int64_t> v, bool is_algosia, size_t n, size_t test_id) {
    test_id = test_id % MAXT;
    std::string s;
    std::vector<bool> xored_str;
    for (const auto val : v) {
        std::vector<bool> my_bools(20);
        for (size_t j = 0; j < 20; j++) {
            if ((val& (1 << j)) == (1<<j)) {
                my_bools[j] = true;
            } else {
                my_bools[j] = false;
            }
        }
        for (const auto bb : my_bools) {
            xored_str.push_back(bb ^ my_bitmask[is_algosia][test_id][xored_str.size()]);
        }
    }
    for (const auto bb : xored_str) {
        if (bb) {
            s += '1';
        } else {
            s += '0';
        }
    }
    for (int i = ((int)(s.size()))-1; i>=0;i--) {
        std::swap(s[i], s[my_swaps[is_algosia][test_id][i]]);
    }
    while (s.size() > n) {
        s.pop_back();
    }
    return s;
}


// returns (score, (algosia, bajtek))
std::pair<int, std::pair<int, int>> my_send3(int my_send, bool is_algosia) {
    std::string st;
    if (my_send == 1) {
        st = "P";
    } else {
        if (my_send == 2) {
            st = "K";
        } else {
            st = "N";
        }
    }
    std::cout << st << '\n';
    std::cout.flush();
    std::string ot;
    std::cin >> ot;
    int their_send = -1000;
    if (ot == "P") {
        their_send = 1;
    } else {
        if (ot == "K") {
            their_send = 2;
        } else {
            their_send = 3;
        }
    }
    
    std::pair<int, int> ab_pair;
    if (is_algosia) {
        ab_pair = std::pair{my_send, their_send};
    } else {
        ab_pair = std::pair{their_send, my_send};
    }
    
    if (my_send == their_send) {
        return std::pair{0, ab_pair};
    }
    if ((st == "P" && ot == "K") ||
        (st == "K" && ot == "N") ||
        (st == "N" && ot == "P")) {
        // I won
        if (is_algosia) {
            return std::pair{1, ab_pair};
        } else {
            return std::pair{-1, ab_pair};
        }
    }
    // I lost
    if (is_algosia) {
        return std::pair{-1, ab_pair};
    } else {
        return std::pair{1, ab_pair};
    }
}

// currently winning sends:
// 1 -> P
// 2 -> K
// currently losing receives:
// P
//
// currently losing sends:
// 1 -> K
// 2 -> P
// currenrly winning receives:
// K

// score, value
std::pair<int, int> my_receive2(int score, bool is_algosia) {
    bool am_i_winning = ((score == 1) && is_algosia) || ((score == -1) && !is_algosia);
    std::string ot;
    if (am_i_winning) {
        std::cout << "K\n";
        std::cout.flush();
        std::cin >> ot;
        if (ot == "K") {
            return std::pair{score, 1};
        } else {
            return std::pair{0, 2};
        }
    } else {
        std::cout << "P\n";
        std::cout.flush();
        std::cin >> ot;
        if (ot == "P") {
            return std::pair{score, 1};
        } else {
            return std::pair{0, 2};
        }
    }
}

// new score
int my_send2(int score, bool is_algosia, int val) {
    bool am_i_winning = ((score == 1) && is_algosia) || ((score == -1) && !is_algosia);
    std::string ot;
    if (am_i_winning) {
        if (val == 1) {
            std::cout << "P\n";
            std::cout.flush();
            std::cin >> ot;
            return score;
        } else {
            std::cout << "K\n";
            std::cout.flush();
            std::cin >> ot;
            return 0;
        }
    } else {
        if (val == 1) {
            std::cout << "K\n";
            std::cout.flush();
            std::cin >> ot;
            return score;
        } else {
            std::cout << "P\n";
            std::cout.flush();
            std::cin >> ot;
            return 0;
        }
    }
}

// score: 
// 1 - algosia winning
// 0 - draw
// -1 - bajtek winning
std::pair<int, std::pair<int64_t, int64_t>> send_int(const int64_t my_int, int64_t a_low, int64_t a_high, int64_t b_low, int64_t b_high, const int score, const bool is_algosia) {
    // TODO: assert score
    int64_t a_length = a_high - a_low + 1;
    int64_t b_length = b_high - b_low + 1;
    if (a_length == 1 && b_length == 1) {
        /*
        if (score != 0) {
            move_to_zero(int score, bool is_algosia);
        }*/
        return std::pair{score, std::pair{a_low, b_low}};
    }
    if (score == 0) {
        int64_t a1_length = a_length / 3;
        int64_t a2_length = (a_length - a1_length) / 2;
        int64_t b1_length = b_length / 3;
        int64_t b2_length = (b_length - b1_length) / 2;

        int64_t what_to_send = -1;
        if (is_algosia) {
            if (my_int < a_low + a1_length) {
                what_to_send = 1;
            } else {
                if (my_int < a_low + a1_length + a2_length) {
                    what_to_send = 2;
                } else {
                    what_to_send = 3;
                }
            }
        } else {
            if (my_int < b_low + b1_length) {
                what_to_send = 1;
            } else {
                if (my_int < b_low + b1_length + b2_length) {
                    what_to_send = 2;
                } else {
                    what_to_send = 3;
                }
            }
        }
        const auto [new_score, ab_res] = my_send3(what_to_send, is_algosia);
        const auto [a_send, b_send] = ab_res;
        // TODO: add assert to check
        if (a_send == 1) {
            a_high = a_low + a1_length - 1;
        } else {
            if (a_send == 2) {
                a_high = a_low + a1_length + a2_length - 1;
                a_low = a_low + a1_length;
            } else {
                a_low = a_low + a1_length + a2_length;
            }
        }

        if (b_send == 1) {
            b_high = b_low + b1_length - 1;
        } else {
            if (b_send == 2) {
                b_high = b_low + b1_length + b2_length - 1;
                b_low = b_low + b1_length;
            } else {
                b_low = b_low + b1_length + b2_length;
            }
        }
        return send_int(my_int, a_low, a_high, b_low, b_high, new_score, is_algosia);
    }

    int64_t new_score = -1000;
    if (a_length < b_length) {
        // b sends
        int64_t what_b_sent;
        const int64_t b1_length = (b_length + 3) / 4;
        if (is_algosia) {
            const auto rr = my_receive2(score, is_algosia);
            new_score = rr.first;
            what_b_sent = rr.second;
        } else {
            int64_t what_to_send = -1;
            if (my_int < b_low + b1_length) {
                what_to_send = 1;
            } else {
                what_to_send = 2;
            }
            new_score = my_send2(score, is_algosia, what_to_send); // what_to_send=2 should go to score=0
            what_b_sent = what_to_send;
        }
        if (what_b_sent == 1) {
            b_high = b_low + b1_length - 1;
        } else {
            b_low = b_low + b1_length;
        }
    } else {
        // a sends
        int64_t what_a_sent;
        const int64_t a1_length = (a_length + 3) / 4;
        if (!is_algosia) {
            const auto rr = my_receive2(score, is_algosia);
            new_score = rr.first;
            what_a_sent = rr.second;
        } else {
            int64_t what_to_send = -1;
            if (my_int < a_low + a1_length) {
                what_to_send = 1;
            } else {
                what_to_send = 2;
            }
            new_score = my_send2(score, is_algosia, what_to_send);
            what_a_sent = what_to_send;
        }
        if (what_a_sent == 1) {
            a_high = a_low + a1_length - 1;
        } else {
            a_low = a_low + a1_length;
        }
    }
    return send_int(my_int, a_low, a_high, b_low, b_high, new_score, is_algosia);
}

void handle_string(std::string current_string, bool is_algosia, size_t test_id) {
    const auto encoded_string = encode_string(current_string, is_algosia, test_id);
    int score = 0;
    std::vector<int64_t> a_vals, b_vals;
    for (const auto val : encoded_string) {
        const auto [new_score, ab_vals] = send_int(val, 0, (1<<20) - 1, 0, (1<<20) - 1, score, is_algosia);
        score = new_score;
        a_vals.push_back(ab_vals.first);
        b_vals.push_back(ab_vals.second);
    }
    if (is_algosia) {
        std::cout << "! " << decode_string(b_vals, false, current_string.size(), test_id) << "\n";
    } else {
        std::cout << "! " << decode_string(a_vals, true, current_string.size(), test_id) << "\n";
    }
    std::cout.flush();
}



int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    build_rands();
    std::string who_am_i;
    int64_t n,t;
    std::cin >> who_am_i >> n >> t;
    bool is_algosia = (who_am_i == "Algosia");
    

    for (size_t i = 0; i < t; i++) {
        std::string current_string;
        std::cin >> current_string;
        handle_string(current_string, is_algosia, 0);
    }
}