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

actions = "PKN"

our: random.Random
opp: random.Random


def act(x: int) -> int:
    print(actions[x], flush=True)
    c = sys.stdin.readline().strip()
    return actions.index(c)


def answer(res) -> None:
    print("! " + "".join(map(str, res)), flush=True)


def solve(_name: str, n: int) -> None:
    global our, opp

    s: list[int] = [int(i) for i in sys.stdin.readline().split()[0]]
    # print(s, file=sys.stderr)
    for i in range(n):
        s[i] ^= our.getrandbits(1)
    f = int("".join(str(i) for i in s), 2)

    mx = 1 << (n + 1) - 1

    val = 0
    pw = 1

    while mx:
        x = f % 3
        f //= 3
        mx //= 3
        t = act(x)

        val += t * pw
        pw *= 3
        if t == x:
            continue

        win = ((x + 1) % 3) == t
        if win:
            assert act(1) == 0
        else:
            assert act(0) == 1
    assert f == 0
    # print("got:", val, file=sys.stderr)

    res = [int(i) for i in bin(val)[2:].zfill(n)]
    # print("=", res, ln, bin(val), file=sys.stderr)
    for i in range(n):
        res[i] ^= opp.getrandbits(1)
    answer(res)


def main() -> None:
    global our, opp
    name = sys.stdin.readline().strip()

    base = 389756127
    delta = ord(name[0]) - ord("A")
    seed1 = base ^ delta
    seed2 = base ^ (1 - delta)

    our = random.Random(seed1)
    opp = random.Random(seed2)

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

    for _ in range(t):
        solve(name, n)


if __name__ == "__main__":
    main()