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
#include <iostream>
#include <random>
#include <string>
int n, k;
using namespace std;
int const MAX_N = 5004;
int message[2][MAX_N];
int other_message[2][MAX_N];
int hands[MAX_N];
int other_hands[MAX_N];
string name;
int gracz;
int main()
{
    cin >> name;
    if (name[0] == 'A') gracz = 0;
    else gracz = 1;
    cin >> n >> k;
    n += 2;
    for (int case_i = 0; case_i < k; case_i++) {
        char c;
        for (int i = 0; i < n; i++) {
            if (i < n - 2) {
                cin >> c;
                if (c == '0') message[0][i] = 0;
                else message[0][i] = 1;
            }
            else {
                message[0][i] = 0;
            }
            message[1][i] = 0;
            other_message[0][i] = 0;
            other_message[1][i] = 0;
            hands[i] = 0;
            other_hands[i] = 0;
        }

        int side = 0;
        int last_hand = 0;
        int rounds = (631 * n) / 1000 + 1;
        for (int k = 0; k < rounds; k++) {
            //DIVISION BY 3
            for (int i = 0; i < n; i++) {
                message[side ^ 1][i] = 0;
            }
            for (int i = 0; i < n - 2;) {
                if (message[side][i] == 1 && message[side][i + 1] == 1) {
                    message[side][i] = 0;
                    message[side][i + 1] = 0;
                    message[side ^ 1][i + 1] = 1;
                    i += 2;
                    continue;
                }
                if (message[side][i] == 1 && message[side][i + 1] == 0 && message[side][i + 2] == 0) {
                    message[side][i] = 0;
                    message[side][i + 1] = 0;
                    message[side][i + 2] = 1;
                    message[side ^ 1][i + 2] = 1;
                    i += 2;
                    continue;
                }

                if (message[side][i] == 1 && message[side][i + 1] == 0 && message[side][i + 2] == 1) {
                    message[side][i] = 0;
                    message[side][i + 1] = 1;
                    message[side][i + 2] = 0;
                    message[side ^ 1][i + 2] = 1;
                    i += 1;
                    continue;
                }
                if (message[side][i] == 0) {
                    i++;
                }
            }
            int last_num = message[side][n - 2] * 2 + message[side][n - 1];
            if (last_num == 3) {
                message[side ^ 1][n - 1] = 1;
            }
            hands[last_hand] = last_num % 3;
            //std::cout << last_num % 3;
            last_hand++;
            side = side ^ 1;
        }

        //std::cout << "\n" << last_hand << "\n";
        char res;
        for (int i = 0; i < rounds; i++) {
            cout << "PKN"[hands[i]] << "\n"; std::cout.flush();
            cin >> res;
            if (res == 'P') other_hands[i] = 0;
            if (res == 'K') other_hands[i] = 1;
            if (res == 'N') other_hands[i] = 2;

            //FIX SCORE IF NOT TIE
            if (other_hands[i] != hands[i]) {
                cout << "PKN"[other_hands[i]] << "\n"; std::cout.flush();
                cin >> res;
            }
        }

        int rem = 0;
        side = 0;
        for (int k = 0; k < rounds; k++) {
            rem = other_hands[rounds - k - 1] + other_message[side][n - 1];
            other_message[side ^ 1][n - 1] = rem % 2;
            rem /= 2;
            for (int i = n - 2; i >= 0; i--) {
                rem += other_message[side][i] + other_message[side][i + 1];
                other_message[side ^ 1][i] = rem % 2;
                rem /= 2;
            }
            side = side ^ 1;
        }
        cout << "! ";
        for (int i = 0; i < n - 2; i++) {
            cout << other_message[side][i];
        }
        cout << "\n";
        std::cout.flush();
    }
}