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

#intervals are [l, r)

def play(c):
    print(c, flush=True)
    return input()

#three intervals of equal length
def split3(interval):
    a, b = interval
    d = b - a
    k = d // 3
    if d % 3 <= 1:
        return [(a, a + k), (a+k, a+2*k), (a+2*k, b)]
    else:
        return [(a, a+k), (a+k, a+2*k + 1), (a+2*k + 1, b)]

#first interval has length 1/4
def split4(interval):
    a, b = interval
    d = b - a
    k = d // 4
    if k == 0:
        k = 1
    return [(a, a + k), (a+k, b)]

def inside(x, interval):
    return interval[0] <= x and x < interval[1]

def siz(interval):
    return interval[1] - interval[0]

def play_code(x):
    if x == 'P':
        return 0
    if x == 'K':
        return 1
    if x == 'N':
        return 2

def calc(my_play, other_play):
    x = play_code(my_play)
    y = play_code(other_play)
    if (x + 1) % 3 == y:
        return 1
    if (y + 1) % 3 == x:
        return -1
    return 0

options = 'PKN'

random.seed(1138930061)
name = input()
n, t = input().split()
n = int(n)
t = int(t)
if name == "Algosia":
    my_mask = random.getrandbits(n)
    other_mask = random.getrandbits(n)
else:
    other_mask = random.getrandbits(n)
    my_mask = random.getrandbits(n)


for iter in range(t):
    string = input()
    code = int(string, 2)
    code ^= my_mask
    my_interval = (0, 2**n)
    other_interval = (0, 2**n)
    score = 0
    while siz(my_interval) > 1 or siz(other_interval) > 1:
        if score == 0:
            x = split3(my_interval)
            my_play = ''
            for i in range(3):
                if inside(code, x[i]):
                    my_play = options[i]
                    my_interval = x[i]
                    break
            other_play = play(my_play)
            other_interval = split3(other_interval)[play_code(other_play)]
            score += calc(my_play, other_play)
        else:
            #i should send information
            if siz(my_interval) > siz(other_interval) or (siz(my_interval) == siz(other_interval) and name == "Algosia"):
                s = split4(my_interval)
                my_play = ''
                if inside(code, s[0]):#short interval
                    my_interval = s[0]
                    if score == 1:
                        my_play = 'P'
                    else:
                        my_play = 'K'
                else:
                    my_interval = s[1]
                    if score == 1:
                        my_play = 'K'
                    else:
                        my_play = 'P'
                other_play = play(my_play)
                score += calc(my_play, other_play)
            else:
                my_play = ''
                if score == 1:
                    my_play = 'K'
                else:
                    my_play = 'P'
                other_play = play(my_play)
                score += calc(my_play, other_play)
                if score == 0:
                    other_interval = split4(other_interval)[1]
                else:
                    other_interval = split4(other_interval)[0]
    other_code = other_interval[0]
    other_code ^= other_mask
    output = bin(other_code)[2:]
    output = output.zfill(n)
    print('!', output, flush=True)