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

ja = 0 if input().strip() == 'Algosia' else 1
on = 1 ^ ja
na_nr = {'P' : 0, 'K' : 1, 'N' : 2}

# logs = open(f'{ja}.err', mode='w')

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

def win(r1, r2):
    return 0 if r1 == r2 else 1 if (r1 + 1) % 3 == r2 else -1

def mowie(x, l, balans):
    r4 = x % 4
    if r4 == 3:
        x = x // 4
        l[ja] -= 2.
        moj_ruch = 'P'
        print(moj_ruch)
        sys.stdout.flush()
        ruch = input().strip()
        balans += win(na_nr[moj_ruch], na_nr[ruch])
    else: # 0 <= r4 <= 2
        x = (x // 4) * 3 + r4
        l[ja] -= 2. - math.log2(3)
        moj_ruch = 'K' if balans == 1 else 'N'
        print(moj_ruch)
        sys.stdout.flush()
        ruch = input().strip()
        balans += win(na_nr[moj_ruch], na_nr[ruch])
    
    # print("mowie", x, l, balans, moj_ruch, ruch, file=logs)
    return x, balans

def czytam(l, ans, balans):
    moj_ruch = 'P'
    print(moj_ruch)
    sys.stdout.flush()
    ruch = input().strip()
    balans += win(na_nr[moj_ruch], na_nr[ruch])

    if ruch == 'P':
        ans.append('11')
        l[on] -= 2.
    else:
        ans.append('sp')
        l[on] -= 2. - math.log2(3)
    

    # print("czytam", l, balans, moj_ruch, ruch, file=logs)
    return balans

def tri(x, l, ans, balans):
    # print("tri_beg", x, file=logs)
    r3 = x % 3
    x //= 3
    
    l[ja] -= math.log2(3)
    l[on] -= math.log2(3)

    moj_ruch = ['P', 'K', 'N'][r3]
    print(moj_ruch)    
    sys.stdout.flush()
    ruch = input().strip()
    balans += win(na_nr[moj_ruch], na_nr[ruch])

    if ruch == 'P':
        ans.append('0')
    elif ruch == 'K':
        ans.append('1')
    else:
        ans.append('2')
    
    # print("tri", x, l, balans, moj_ruch, ruch, file=logs)
    return x, balans

def solve(n):
    key = random.getrandbits(n)
    x = int(input().strip(), 2) ^ key
    l = [n + 15, n + 15]
    balans = 0
    ans = []

    while l[ja] > 0 or l[on] > 0:
        if balans == 0:
            x, balans = tri(x, l, ans, balans)
        elif l[0] + 1 > l[1]:
            if ja == 0:
                x, balans = mowie(x, l, balans)
            else: # ja == 1
                balans = czytam(l, ans, balans)
        else: # l[0] <= l[1]
            if ja == 1:
                x, balans = mowie(x, l, balans)
            else: # ja == 0
                balans = czytam(l, ans, balans)

    y = 0
    for i in ans[::-1]:
        if len(i) == 2:
            if i == 'sp':
                r3 = y % 3
                y = (y // 3) * 4 + r3
            else:
                y = y * 4 + int(i, 2)
        else:
            y = y * 3 + int(i)
    y ^= key

    print(f"! {y:0{n}b}")
    # print(ans, file=logs)
    # print(f"! {y:0{n}b}", file=logs)
    sys.stdout.flush()


random.seed(800813569420)
while t:
    # print(f"TEST {t}", file=logs)
    solve(n)
    t -= 1

# logs.flush()
# logs.close()