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
import sys, random

random.seed(2026)

whoami = sys.stdin.readline().strip()
is_algosia = whoami == 'Algosia'

#print('isa', is_algosia)

n, t = map(int, sys.stdin.readline().strip().split(' '))

dact_1 = {'000':'P', '001':'P', '010':'P', '011':'N', '100':'N', '101':'N', '110':'K', '111':'K'}
dact_2 = {'000':'P', '001':'K', '010':'N', '011':'P', '100':'K', '101':'N', '110':'P', '111':'K'}

rev_dact = {}
for k in dact_1:
    rev_dact[dact_1[k]+dact_2[k]] = k

for nT in range(t):
    inpt = sys.stdin.readline().strip()    
    buf = ['0']*(n+2)
    exor = [random.randint(0, 1) for _ in range(n)]
    data = [inpt[i] if exor[i]==0 else ('1' if inpt[i]=='0' else '0') for i in range(n)]

    #print('dat ', data)

    data.extend(['0', '0'])
    
    i, j = 0, n
    diff = 0
    halflife3 = False
    hl3_confirmed = None
    rechot = 0
    ja_nadaje = True
    while i < j:
        if diff == 0:
            dactyl = ''.join(data[i:i+3])
            x = (dact_2 if halflife3 else dact_1)[dactyl]
        else:
            my_adv = diff > 0
            ja_nadaje = (is_algosia == bool(rechot%2))
            if ja_nadaje:
                if data[j-1] == '0':
                    x = 'P'
                else:
                    x = 'K' if my_adv else 'N'
            else:
                x = 'P'

        print(x)
        y = sys.stdin.readline().strip()            

        if diff == 0:
            halflife3 = not halflife3
            if halflife3:
                hl3_confirmed = y
            else:
                buf[i:i+3] = rev_dact[hl3_confirmed + y]
                i += 3
        else:
            if not ja_nadaje:
                buf[j-1] = ('0' if y == 'P' else '1')
            rechot += 1
            if rechot % 2 == 0:
                j -= 1

        if x != y:
            diff += (-1 if (x=='P' and y=='N') or (x=='N' and y=='K') or (x=='K' and y=='P') else 1)

    #print('buf ', buf)

    outpt = [buf[i] if exor[i]==0 else ('1' if buf[i]=='0' else '0') for i in range(n)]

    print("! %s" % ''.join(outpt))