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
import sys
from math import *

def ruch(x):
  s = "PKN"
  print(s[x])
  sys.stdout.flush()
  x = input()
  return s.find(x)

def wyslij(win, x):
  on = ruch(x)
  if win == 1:
    assert on == 0
    return 0 if x == 1 else 1
  else:
    assert on == 1
    return 0 if x == 0 else 2

def sluchaj(win):
  if win == 1:
    on = ruch(1)
    return 0 if on == 0 else 1
  else:
    on = ruch(0)
    return 0 if on == 1 else 2

magia = 106484188261364045237315513089735604441863467659708352764976038514374494444221296032408773398133418043558012821881715604520442700064258538554882032676373503803328736698348219543810306732759082349679721534219693660075806059046995527009111957250227486236626104418502032322246835760490807172311251213932575854003462312689415099677829209678032919146570268923007876861754465975670885612864887870849164808547821202713297941145388672530461173042603124075570699828021255955711515403464736959336508646795067179893713496697410472963691473524266034724318795649371341648876469768359530817384421256651669818497986730945079740273483017842446918054842468812387423495078407814058703621059892009506843556733381894825850433154188642024565086506312456009190849219647622157723042496853488854179585321872292686983347783288922234160810311762657815752866628720733923988547958035411145894825753499478170754093678041851822411189609262318000683000709163989402389980244151482117617051287951936703635926860759908318030545287073743263537289878855901253870917068734300818383002150676997967907657334625789782669997394581675332745867956079361229273738357453075326442221366391460325939352920647529668697500021721864298898634194805761231664361283802964433893808602717764594824978046201488421211221592613354712238331264907380098078713549633222373393938063980369934877962124631048961840191735161640061042460414581032421245296756895653166406843066815179283660402310462428218075825247947603180742017378796463752063239804516626670368689260765330
def dajmagie(n):
  return magia & (2**n-1)

alicja = False
tr = log2(3)
eps = -1

def solve(n):
  s = input()
  a = 0
  for i in range(n):
    a = 2 * a + (1 if s[i] == '1' else 0)
  a ^= dajmagie(n)

  cyfry = []
  i = n
  j = n
  win = 0
  while i > eps and j > eps:
    ja = a % 3
    a //= 3
    on = ruch(ja)
    cyfry.append((on, 0))
    i -= tr
    j -= tr
    win = (on + 3 - ja) % 3
    if win == 0:
      continue
    while i > eps and j > eps and win != 0:
      stary = win
      if i > j or (i == j and alicja):
        x = a % 3
        a //= 3
        if x == 2:
          win = wyslij(win, 0 if win == 1 else 1) # zremisuj
          assert win == stary
          i -= tr
        else:
          win = wyslij(win, 1 if win == 1 else 0) # zresetuj
          assert win == 0
          a = 2 * a + x
          i -= tr
          i += 1
      else:
        win = sluchaj(win)
        if stary == win: # zremisowalismy, czyli 2
          cyfry.append((2, 0))
          j -= tr
        else:
          # zresetowalismy, czyli 01
          assert win == 0
          cyfry.append((0, 1))
          j -= tr
          j += 1

  if win == 1:
    ruch(1)
  elif win == 2:
    ruch(0)

  while i > eps:
    ja = a % 3
    a //= 3
    on = ruch(ja)
    i -= tr
    win = (on + 3 - ja) % 3
    if win == 1:
      ruch(1)
    elif win == 2:
      ruch(0)
  while j > eps:
    ja = 0
    on = ruch(0)
    cyfry.append((on, 0))
    j -= tr
    win = (on + 3 - ja) % 3
    if win == 1:
      ruch(1)
    elif win == 2:
      ruch(0)

  cyfry = cyfry[::-1]

  liczba = 0
  for c, p in cyfry:
    if p == 0:
      liczba = liczba * 3 + c
    else:
      liczba = (liczba // 2) * 3 + (liczba % 2)
  liczba ^= dajmagie(n)

  odp = ""
  for i in range(n):
    odp += '1' if liczba % 2 == 1 else '0'
    liczba //= 2
  odp = odp[::-1]

  print(f"! {odp}")
  sys.stdout.flush()

kto = input()
if kto[0] == 'A':
  alicja = True
n, t = map(int, input().split())
for i in range(t):
  solve(n)