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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdint>
#include <cassert>
#include <algorithm>

// 19 bits can be encoded as 12 trits
uint32_t encode_bits_as_trits(uint32_t bits) {
    uint32_t trits = 0;
    uint32_t shift = 0;
    uint32_t powof3 = 1;
    while (powof3 <= bits) {
        powof3 *= 3;
        shift += 2;
    }
    while (powof3 > 1) {
        powof3 /= 3;
        shift -= 2;

        if (bits >= 2 * powof3) {
            trits |= 2 << shift;
            bits -= 2 * powof3;
        } else if (bits >= 1 * powof3) {
            trits |= 1 << shift;
            bits -= 1 * powof3;
        }
    }

    assert(bits == 0);
    return trits;
}

uint32_t encode_trits_as_bits(uint32_t trits) {
    uint32_t result = 0;
    uint32_t powof3 = 1;
    while (trits > 0) {
        uint32_t digit = trits & 3;
        result += digit * powof3;
        trits >>= 2;
        powof3 *= 3;
    }
    return result;
}

int trits_necessary_for_bits(int num_bits) {
    uint32_t bits = (1 << num_bits) - 1;
    uint32_t trits = encode_bits_as_trits(bits);
    int num_trits = 0;
    while (trits > 0) {
        num_trits += 1;
        trits >>= 2;
    }
    return num_trits;
}

uint32_t exchange(uint32_t my_trit, const char* name) {
    char my_char;
    switch (my_trit) {
        case 0: my_char = 'P'; break;
        case 1: my_char = 'K'; break;
        case 2: my_char = 'N'; break;
        default: assert(false);
    }

    printf("%c\n", my_char);
    fflush(stdout);

    // fprintf(stderr, "%s: I have sent %c\n", name, my_char);

    char other_char[16];
    scanf("%s", other_char);

    // fprintf(stderr, "%s: I received %c\n", name, other_char[0]);

    switch (other_char[0]) {
        case 'P': return 0;
        case 'K': return 1;
        case 'N': return 2;
        default:
            fprintf(stderr, "Wrong char code: %d\n", (int)other_char[0]);
            assert(false);
    }
}

char sequence[5000 + 42];
char other_sequence[5000 + 42];

static void solve_one(const int n, const char* name) {
    scanf("%s", sequence);

    const int CHUNK_SIZE = 19;
    for (int chunk_begin = 0; chunk_begin < n; chunk_begin += CHUNK_SIZE) {
        const int chunk_end = std::min(n, chunk_begin + CHUNK_SIZE);
        const int num_trits = trits_necessary_for_bits(chunk_end - chunk_begin);

        uint32_t my_bits = 0;
        for (int i = chunk_begin; i < chunk_end; i++) {
            if (sequence[i] == '1') {
                my_bits |= 1 << (i - chunk_begin);
            } else {
                assert(sequence[i] == '0');
            }
        }
        const uint32_t my_trits = encode_bits_as_trits(my_bits);
        // fprintf(stderr, "%s: My trits: %d, my binary chunk: %d, num trits: %d\n", name, my_trits, my_bits, num_trits);
        uint32_t other_trits = 0;
        for (int i = 0; i < num_trits; i++) {
            const uint32_t my_digit = (my_trits >> (2 * i)) & 3;
            // fprintf(stderr, "%s: My digit: %d\n", name, my_digit);
            const uint32_t other_digit = exchange(my_digit, name);
            other_trits |= other_digit << (2 * i);

            if (my_digit != other_digit) {
                // Exchange the bit back, the other side will do the same
                // and we will get back to zero balance this way.
                exchange(other_digit, name);
            }
        }

        const uint32_t other_bits = encode_trits_as_bits(other_trits);
        for (int i = chunk_begin; i < chunk_end; i++) {
            other_sequence[i] = (other_bits & (1 << (i - chunk_begin))) ? '1' : '0';
        }
    }

    // fprintf(stderr, "%s: ", name);
    // fwrite(other_sequence, sizeof(char), n, stderr);
    // fputc('\n', stderr);

    printf("! ");
    fwrite(other_sequence, sizeof(char), n, stdout);
    putchar('\n');
    fflush(stdout);
}

int main() {
    char name[32];
    fgets(name, sizeof(name), stdin);
    // for (int i = 0; i < 32; i++) {
    //     if (name[i] == '\n') {
    //         name[i] = '\0';
    //     }
    // }
    // Ignore the name, we operate symmetrically

    int n, t;
    scanf("%d %d", &n, &t);

    while (t --> 0) {
        solve_one(n, name);
    }

    return 0;
}