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

mti = {
	'P' : 0,
	'K' : 1,
	'N' : 2,
}

itm = {
	0 : 'P',
	1 : 'K',
	2 : 'N',
}

random.seed(424242)

name = input()

n, t = map(int, input().split())
iterations = math.ceil(n * math.log(2, 3)) + 1

for _ in range(t):
	myNum = int(input(), 2)
	myNumCopy = myNum
	otherNum = 0
	base = 1

	for iter_idx in range(iterations):
		offset = random.randrange(0, 3)

		myNum, myMoveI = divmod(myNum, 3)
		myMove = itm[(myMoveI + offset) % 3]

		print(myMove)
		sys.stdout.flush()

		otherMove = input()
		otherMoveI = (mti[otherMove] + 3 - offset) % 3

		otherNum += base * otherMoveI
		base *= 3

		if iter_idx != iterations - 1 and otherMove != myMove:
			print(otherMove)
			sys.stdout.flush()
			temp = input()

	print(f"! {otherNum:0{n}b}")
	sys.stdout.flush()