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

def to_base(x, l, digits):
    res = []
    base = len(digits)
    for i in range(l):
        res.append(digits[x % base])
        x //= base
    return ''.join(reversed(res))

def to_num(c):
    if c == 'P':
        return 0
    elif c == 'N':
        return 1
    else:
        return 2
    
def to_digit(c):
    if c == 'P':
        return '0'
    elif c == 'N':
        return '1'
    else:
        return '2'  
    
def beats(a, b):
    if to_num(a) == (to_num(b) + 1) % 3:
        return True
    return False

def maxlen(n):
    val = (1 << n) - 1
    l = 0
    while val:
        l += 1
        val //= 3
    return l

imie = input().strip()
n, t = map(int, input().split())

l = maxlen(n)

for q in range(t):
    x = int(input().strip(), 2)
    s = to_base(x, l, "PNK")
    # print("s = ", s)
    p = []
    bilans = 0
    for i in range(len(s)):
        if bilans < 0: # przegrywam - mam wygrać
            print('K')
            c = input().strip()
            bilans += 1
        elif bilans > 0: # wygrywam - mam przegrać
            print('N')
            c = input().strip()
            bilans -= 1
        
        print(s[i])
        c = input().strip()
        p.append(c)

        if beats(s[i], c):
            bilans += 1
        elif beats(c, s[i]):
            bilans -= 1
        # print("bilans ", bilans)
    

    # print(p)
    p2 = ''.join([to_digit(el) for el in p])
    # print("cyfry 3L ", p2)
    # print("liczba 10: ", int(p2, 3))
    print("!", to_base(int(p2, 3), n, "01"))
    sys.stdout.flush()