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

name = input()
n, t = map(int, input().split())

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

seed(56756757)

for _ in range(t):
  secret = 0
  rng = []
  for c in input(): 
    secret *= 2
    rng.append(randint(0, 1))
    secret += (ord(c) - ord('0')) ^ rng[-1]

  myL, myR = 0, 2 ** n
  opL, opR = 0, 2 ** n
  diff = 0

  while myR - myL > 1 or opR - opL > 1:
    #print(myR - myL, opR - opL, diff, file=sys.stderr)
    #print(f"{diff=}", file=sys.stderr)

    if diff == 0:
        A = myL + (myR - myL + 2) // 3
        B = A   + (myR - myL + 2) // 3
      
        if secret < A:
          out, myR = itoc[0], A
        elif secret < B:
          out, myL, myR = itoc[1], A, B
        else:
          out, myL = itoc[2], B
       
        #print(f"printing {out=}", file=sys.stderr) 
        print(out)
        sys.stdout.flush()
        #print(f"hello", file=sys.stderr) 
        inp = input()

        A = opL + (opR - opL + 2) // 3
        B = A   + (opR - opL + 2) // 3

        if ctoi[inp] == 0:
          opR = A
        elif ctoi[inp] == 1:
          opL, opR = A, B
        else:
          opL = B

        if out != inp:
          if (out+inp) in {"PK", "KN", "NP"}: 
            diff += 1
          else:
            diff -= 1  
    else:
      my = myR - myL
      op = opR - opL

      if my > op or (my == op and name == "Algosia"):
        A = myL + (myR - myL + 2) // 3 
         
        if diff == -1:
          if secret < A:
            out, myR = "P", A
          else:
            out, myL = "N", A
        else:
          if secret < A:
            out, myR = "P", A
          else:
            out, myL = "K", A
        
        print(out)
        sys.stdout.flush()
        inp = input() 

        if out != inp:
          diff = 0
      else: 
        print("P")
        sys.stdout.flush() 

        A = opL + (opR - opL + 2) // 3

        inp = input()
        if inp == "P":
          opR = A
        else:
          opL = A

        if inp != "P":
          diff = 0
 
  ans = [-1 for i in range(n)]

  for i in range(n-1, -1, -1):
    ans[i] = rng[i] ^ (opL % 2)
    opL //= 2  
 
  print("! ", end='')
  for i in range(n):
    print(ans[i], end='') 
  print()
  sys.stdout.flush()