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

person = input()
line = input()
values = line.split(" ")
n = int(values[0])
t = int(values[1])

toLet = {
	0: "P",
	1: "K",
	2: "N",
}

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

com_seed = 2**9 - 1

random.seed(com_seed)

random.randint(1, 10)

def game():
	global number, workingnumber, guess, mult, score, alg, nextAlg, com_seed, xorA, xorB, my_multi, their_multi, bound

	number = int(input(), 2)
	workingnumber = number
	guess = 0
	mult = 1

	score = 0
	alg = False
	nextAlg = True
	com_seed = 0
	xorA = 0
	xorB = 0
	my_multi = 1
	their_multi = 1
	bound = 2**n

	def winning() -> int:
		return score > 0
	def losing() -> int:
		return score < 0

	def play(my):
		global score
		print(f" {my}")
		their = input()
		if (my == their):
			return their
		if ((toVal[my] + 1) % 3 == toVal[their]):
			score+=1
		else:
			score-=1
		return their

	def safeSend(bit: int) -> int:
		l = toLet[bit + winning()]
		play(l)

	def safeReceive():
		old_losing = losing()
		l = play("K")
		v = toVal[l] - old_losing
		return v

	def equalize():
		my = "P"
		if (score > 0):
			my = "K"
		play(my)

	def sendTrites():
		global workingnumber, guess, my_multi, their_multi
		tosend = workingnumber % 3
		workingnumber = workingnumber // 3
		rec = play(toLet[tosend])
		guess += toVal[rec] * their_multi
		my_multi *= 3
		their_multi *= 3

	def sendByte():
		global workingnumber, guess, my_multi, their_multi, nextAlg, alg
		if (nextAlg == alg):
			tosend = workingnumber % 2
			workingnumber = workingnumber // 2
			safeSend(tosend)
			my_multi *= 2
		else:
			rec = safeReceive()
			guess += rec * their_multi
			their_multi *= 2
		nextAlg = not nextAlg

	if (person == "Algosia"):
		alg = True
	else:
		alg = False

	# if (alg):
		# random.seed()
		# for i in range(5):
			# v = random.randrange(2)
			# com_seed = com_seed * 2 + v
			# safeSend(v)
	# else:
		# for i in range(5):
			# v = safeReceive()
			# com_seed = com_seed * 2 + v

	xorA = random.getrandbits(n)
	xorB = random.getrandbits(n)

	# eprint(("xorA {:0" + str(n) +"b}").format(xorA))
	# eprint(("xorB {:0" + str(n) +"b}").format(xorB))

	if (alg):
		number = number ^ xorA
	else:
		number = number ^ xorB

	workingnumber = number

	while (my_multi < bound or their_multi < bound):
		if (score == 0):
			sendTrites()
		else:
			sendByte()

	if (alg):
		guess = guess ^ xorB
	else:
		guess = guess ^ xorA

	print(("! {:0" + str(n) +"b}").format(guess))


for i in range(t):
	game()