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
#!/usr/bin/env python3
import math
import random
import sys

random.seed(9876)
sys.set_int_max_str_digits(54321)

def pad(n, s):
  return '0' * (n-len(s)) + s

def base3(n, x):
  t = []
  for _ in range(n):
    x, r = divmod(x, 3)
    t.append(r)
  return t[::-1]

def conv32(n, s):
  return pad(n, bin(int(''.join(map(str, s)), 3))[2:])

def mul(p, n):
  m = 10**18
  return int(p*m) * n // m

def split_range(lo, hi, *ps):
  return [lo] + [math.floor(lo + mul(p, hi-lo)) for p in ps] + [hi]

item = 'PKN'

alpha = 0.239788468
def ps(k):
  return [] if k == 1 else [1-alpha] if k == 2 else [1/3, 2/3]

who = input()
n, tc = map(int, input().split())
m = math.ceil(n * math.log(2, 3))

for _ in range(tc):
  s = base3(m, int(input(), 2))
  salt = [random.randrange(3) for _ in range(2*m)]
  s = [(x+y) % 3 for x, y in zip(s, salt[:m] if who[0] == 'A' else salt[m:])]
  s = int(''.join(map(str, s)), 3)
  score = 0
  alo, ahi = 0, 3**m
  blo, bhi = 0, 3**m
  while ahi-alo > 1 or bhi-blo > 1:
    # print(who, score, alo, ahi, blo, bhi, file=sys.stderr)
    if score == 0:
      opta, optb = [0, 1, 2], [0, 1, 2]
    elif max(ahi-alo, bhi-blo) < 10:
      opta = [1] if score > 0 else [0]
      optb = [0] if score > 0 else [1]
    elif (ahi-alo, who[0]) > (bhi-blo, 'A' if who[0] == 'B' else 'B'):
      opta = [1, 0] if score > 0 else [0, 1]
      optb = [0] if score > 0 else [1]
    else:
      opta = [1] if score > 0 else [0]
      optb = [0, 1] if score > 0 else [1, 0]

    # da > db, score > 0: me = 1, 0, you = 0
    # da > db, score < 0: me = 0, 1, you = 1
    # da < db, score > 0: me = 1, you = 0, 1
    # da < db, score < 0: me = 0, you = 1, 0

    # print(ps(len(opta)), file=sys.stderr)
    stepa = split_range(alo, ahi, *ps(len(opta)))
    stepb = split_range(blo, bhi, *ps(len(optb)))

    posa = 0
    while stepa[posa+1] <= s:
      posa += 1
    assert stepa[posa] <= s < stepa[posa+1]

    me = opta[posa]
    print(item[me], flush=True)
    you = item.index(input())
    posb = optb.index(you)

    alo, ahi = stepa[posa], stepa[posa+1]
    blo, bhi = stepb[posb], stepb[posb+1]

    score += (you-me+1) % 3 - 1
    assert -1 <= score <= 1

  t = base3(m, blo)
  t = [(x-y) % 3 for x, y in zip(t, salt[m:] if who[0] == 'A' else salt[:m])]
  print('!', conv32(n, t), flush=True)