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
#!/usr/bin/env python3

# Author : Jakub Rożek
# Task   : PKN - Papier, kamień, nożyce [A]
# Time   : n * A
# Memory : A
# A to bigint

import sys


WEIGHTS_0 = [1, 1, 1]
WEIGHTS_1 = [2398, 7602]
MASK_A = "00011111110100011110001110011001101000001001011100001011100111110111010010001011000101000001100010000111011001110100111001011011000110001001001001001010110000000010000001100101100110010000100011001010101011010110111001001101110101001011111000000001000001111111001110110011111010001110001001100010111000101000100001010000110100111101000001001011001111011000100110101111011001101111001100011001111010101001111101100011011010010111000011000011000111001000111111000010101001111001000111111111010000101011100101100110101000010101111001011010001010000101111000001011001110110010011000000100110000001010011001001101001000001000001000101101000001011100010000100110100000010011000010000001010101101100000001001000110111000011011101100101001110001011101100010011101000100011110011110111011000000100010111011100110110000110000010110100100010010001010010010011010010011110001100101000101011011111001000001111010111100001000100001100010111001101001001100100101010101001101011010100001011000011011010000011000001100001000100000111000001100100000010011001111111011110001101111110000001111000101100000011110000001010000010000011110000010100011100101001011000100110011001110100101110000011000111110011101110101001000000011001011111010000100100110110000001011100110111010001101010011101001011000111101100110011110100100111011110011110101101011000011101101110101001100000011010011011011100101101000100010101010000010101010010001110110111000000011010101011010111110001001001011110101010001001001001111111101011110000101111010000111111110101100000010001111010101111110000111000010100101010000111101110010010000011010110101010111110011010111111101100010000111000001001111101110110110011100011011001100101111011010001111101010101100111000101111010011001111111110101110001011011010010100100011111110101101111111001010100101111000010100101010110011001101100101100010100001111100000010000110001000010001000010010001001001110111011101110010011010011001010000011110111111110111010000100111011010011000111101000101110110001010110000011111000001011101101100011110111101010111101100001010100110011100000010110110110100000010001001000100011000000001010100110110100111100111110101001000111101110110101001101111101010110001101011001100101001111011011001100111101000011010110100111000001111010010100100000010101001100110101001100110100110100110000101101110100010001100100110110101100011000011100001010011101001011010001000100101111001001010000000001101001010001010010110010110100100010100110011001001001011101011000100010100101100110101100100111101011100110111110000111111010001111000011001111001100010000011110101101001001010001000011011001101110001001010000000010110111110111100001000010001011101001100011111000111001111101111001011111000101000001011100001000011100010110010001111010111101110100100011000101111011000100001000100100110001000010001111000000111100010011111001101111010010011001111001011011101001111010111000100010010001001110111010111111100011111111000010011110111101111110010001100000111111011001001100101010101101111111100111101110110001100011110110001111110001001110101110000110000111001110100100100001100101100100110001111010110000110110100000001001110010010011010011101000110011010011110100000111111001111001001100010001001111101001011011100110101101111001010110000101101111101000001100111000101010111001110101111000111110110101101010010100110100110111100101110000100110101010001010000110001010101001111010010110111110000010000110101001001111010000101000111010101001001010110010011001011100100001111111110010101001101010010001101001110001010111001010010111100111011100101001011000100000001011010100000000111111110101110111000000001000111110100001100001010111110111000000101111001011001001111011101001110010101001011110001001100010111011110101100110010010001010010000000010011010000111110010011111000101001111000000100011111100110101000010111000110010010011100101010001011001100001101001010000101101100111101011010010010101101000101001111011001110111011010100011001011010010101011011110010000000010001001010000111111000001110001111110111101010000000110101011010010001101000010011101100000011001011111001100100101001111111100111000000101100110010010110110111100001100011100101001100010101011000111011001010001110000110111010010110010111101101111111001111110011010001100101100000000001110001100111001101100100100010001111111101110000000110110001101100010100111000011101001101010010000000101110101000010010110001010100100000011101110011011010110001010110111100100011000011101000110010010111001001111100100001110101000101001000010101100010011010101001110011111100101101101001111001011100010100111010101101110000101100000000110110101011100100010000100100101100010100011101001010100011111101010000101111101110000000101110011001011100111111010001011000010001110001010101110101001101011001111011000010010100100100101001010111000110100000100110111001010111111110001110000010111001100001100000101110010110101101011111010010000110110100011100100001011010111000100100110100100100100010110001100010111110110111001100101001001101"
MASK_B = "01011011100000101110000111110001010111011111001010110010100010001000001100011000010101001001000110010000001110011001111010101110010000010100110000110001001110001101111100101111100100100110110111000000101110011111101101010110111011000000010010010111001110111011001100111010100111101101010001010000101100010111001111000110011001001110110011110100000110110010011010110101111111010010000100000101011111100011001001010111010110111100111011111000010001000111001000111001111010110010000110110100100100100001001110100101101111011000011110111101000011011000001110001101011110111111011101010101010011101100011111100011010011000101100000111110001100001000011100100000011100111100101110010110111010010100000011111111100010000100000010000000011100110011101100000010010100100001011110111001010011110111010110010011001010001000011100011100110010101011011000001110001101100111010100110111011001100010000111101110010101111100110110110110110011101110111011110110011011000111000111111110010010111101111010110110110100100111000110101101010111011010000100000111101011001000011110101110010100010000101100010001000111110101111100011101011100110000001011001011001110100111001001011000010111101001101100101000100110101111001011011100001101111000111010000011010011010101100010001110011011110100110011101100100000011011010011001111010011000110011000000000101111000010001000000000010011011000100001010101111110100010100010111101100111101110111111011101001101111101110100111100100101001011101010101011011101000110110110111110110010011000110010101010100010111010011100110101101111001000101111010000101111001011000101000011111001100001010110111111100111010101111100011101011001010110001111100011001011010010001101011111100111100001011000001011010111100100101001001011101001100000000000000110100011010001111000100011100110100101011001000110010110011010100110010011011111111010011000010110100100111110001001010110110000000110100100011101001001100010101100011100010010101110011010011010011010110111000110010000101101010110011001111001110101101010110000001101110000011001110110000111110110111000011111011000111000011110100110011100100101101100010100110001110110100011100100010100000011101100001100011100100100111001101001011101010010000110110110101101011010101100110001111110101011110011011100000000101110011111000111111001010101000000011011101010000100011100011001101100011011011100101100011010010101111000100111100100010100101100110010001110000011010000101100000000101100101101101110100100100010100101111111000011110001101101001000100011010100110111100101000110101110011011111000011100000100100010100001110001011011110111010011101000001100000010101010111001101000010100001111101111001010100100000100010010110010000001001111010000011101011001010111100110010110000001010100010101001111110010000111010111111000100010001011101010011010001000000110110100010110001100010101111110001110100010101001100010011000000110011101011001000110011000111011010011000011001000001010111000100111010000000010110011011110010011010100101100001001111001101000011111110001011010110011110010100110000000101000010011100101010101100011111110010000100000110101010111100010110111110110110000100111010101001110101011001001011000000101111101111001111010110111001111001111001000100110111000001111111001000111000100001100011100111001000011000011001000000010100110000100100000000100110000010000011110100110110010101110101010000100010010011111000111110001010000010111010001001010011011101110011001100111100011110011001010001111011010110000100101110100010101010111100011110011101111011000001000100011101111000011010000010010111111011011110010100001011000001010010100111001111010011011100110001101101010000101101110100001010101101011001100101110011010011010111111100111101110001110010001011001011010111011001010001000001010000001010110100101000100111000000000011111000000101110100000000010110000011100100011111001110100111011100100001110110100110110101101010101010111110001101000010111010001000110101100111011111001001001100101011110111111110010011010001000100111001100001101011010000111111010111110010010101010001101111010000001011110110001010000011001001001110000001011101001000001011011111100111101101001111100111100010110001111100100111001010001110000100000001101000010100101110111111010010101001001001100011101110111101011110100111011100011001000011101110111001010000001011000101110001101110000100001000110111010111010100010111100111101100001000011101000000101001011011110010001100110100011011000100001000000110111111010011110011000100000111110011010010101000000010011100001111101001111111010011110010011111001110111010100011111001111011111000110100101010000110011110101001110000011010110111101011001000010001001000110011110000001011111101000001101100101011001001010011110000011101000001001010000010101111101001101100000100101101111000010111001100010010100100111111110010110011101001100100010100011100110010100011011001011001000101110111011101000100010111000111111111010000110111011010101001010101001111011100101101110101101000000010000010001011001001000001100000111"


def split(rng: tuple[int, int], weights: list[int]) -> list[tuple[int, int]]:
    lo, hi = rng
    length = hi - lo
    parts = len(weights)
    total_weight = sum(weights)

    base = [0] * parts
    remaining = length

    if length >= parts:
        for i in range(parts):
            base[i] = 1
        remaining -= parts
    else:
        order = sorted(range(parts), key=lambda i: (-weights[i], i))
        for i in range(length):
            base[order[i]] = 1
        remaining = 0

    extra = [(remaining * w) // total_weight for w in weights]
    remainders = [(remaining * w) % total_weight for w in weights]
    remaining -= sum(extra)
    for i in range(parts):
        base[i] += extra[i]

    order = sorted(range(parts), key=lambda i: (-remainders[i], i))
    for i in range(remaining):
        base[order[i]] += 1

    result: list[tuple[int, int]] = []
    current = lo
    for v in base:
        result.append((current, current + v))
        current += v
    return result


def locate(parts: list[tuple[int, int]], value: int) -> int:
    for i in range(len(parts) - 1):
        if value < parts[i][1]:
            return i
    return len(parts) - 1


def move_id(c: str) -> int:
    if c == "P":
        return 0
    if c == "K":
        return 1
    return 2


def move_char(idx: int) -> str:
    return "PKN"[idx]


def delta_score(move_a: int, move_b: int) -> int:
    if move_a == move_b:
        return 0
    if (move_a + 1) % 3 == move_b:
        return 1
    return -1


def build_masks(n: int) -> list[str]:
    return [MASK_A[:n], MASK_B[:n]]


def xor_word(word: str, mask: str) -> str:
    return "".join("1" if word[i] != mask[i] else "0" for i in range(len(word)))


def solve_case(PERSON, N, masks) -> None:
    my_word = xor_word(sys.stdin.readline().strip(), masks[PERSON])
    my_value = int(my_word, 2)
    limit = 1 << N
    range_a = (0, limit)
    range_b = (0, limit)
    state = 0

    while range_a[1] - range_a[0] != 1 or range_b[1] - range_b[0] != 1:
        size_a = range_a[1] - range_a[0]
        size_b = range_b[1] - range_b[0]
        a_sends = size_a > size_b or (size_a == size_b and PERSON == 0)
        ranges_a = []
        ranges_b = []

        if state == 0:
            ranges_a = split(range_a, WEIGHTS_0)
            ranges_b = split(range_b, WEIGHTS_0)
        else:
            ranges_a = split(range_a, WEIGHTS_1)
            ranges_b = split(range_b, WEIGHTS_1)

        if state == 0:
            move_a = locate(ranges_a, my_value)
        elif a_sends:
            if state == 1:
                move_a = 1 if locate(ranges_a, my_value) == 0 else 2
            else:
                move_a = 1 if locate(ranges_a, my_value) == 0 else 0
        else:
            move_a = 1

        print(move_char(move_a), flush=True)
        move_b = move_id(sys.stdin.readline().strip())

        if state == 0:
            range_a = ranges_a[move_a]
            range_b = ranges_b[move_b]
        elif a_sends:
            range_a = ranges_a[0 if move_a == 1 else 1]
        else:
            range_b = ranges_b[0 if move_b == 1 else 1]

        state += delta_score(move_a, move_b)

    answer = xor_word(bin(range_b[0])[2:].zfill(N), masks[1 - PERSON])
    print("! " + answer, flush=True)


def main() -> None:
    PERSON = 0 if sys.stdin.readline().strip() == "Algosia" else 1
    N, T = map(int, sys.stdin.readline().split())
    masks = build_masks(N)
    for _ in range(T):
        solve_case(PERSON, N, masks)


if __name__ == "__main__":
    main()