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
145
146
147
148
149
150
# Zadanie: PKN (Papier Kamien Nożyce)
# runda 2
# Marcin Machura <marcin.machura@hotmail.com>
import sys

input = sys.stdin.readline


def beats(first, second):
    return (
        (first == 'P' and second == 'K')
        or (first == 'K' and second == 'N')
        or (first == 'N' and second == 'P')
    )


def round_result(mine, opp):
    if mine == opp:
        return 0
    if beats(mine, opp):
        return 1
    return -1


def play_round(move):
    print(move, flush=True)
    return input().strip()


def choose_sender(balance, rem_a, rem_b):
    # B
    if rem_a == 0:
        return 'B'
    if rem_b == 0:
        return 'A'
    if balance == 1:
        return 'B'
    if balance == -1:
        return 'A'
    return 'A' if rem_a >= rem_b else 'B'


def sender_base_move(sender):
    return 'P' if sender == 'A' else 'K'


def sender_one_move(sender, sender_leading):
    if sender == 'A':
        return 'K' if sender_leading else 'N'
    return 'N' if sender_leading else 'P'


def phase_c_move(bit, active_leading):
    # C
    if bit == '0':
        return 'N'
    return 'P' if active_leading else 'K'


def main():
    role = input().strip()
    n, t = map(int, input().split())
    is_algosia = role == 'Algosia'

    for _ in range(t):
        my_word = input().strip()

        sent = 0
        received = 0
        opp_word = ['?'] * n
        balance = 0

        while sent < n or received < n:
            if is_algosia:
                rem_a = n - sent
                rem_b = n - received
            else:
                rem_a = n - received
                rem_b = n - sent

            # C
            only_a_left = rem_a > 0 and rem_b == 0
            only_b_left = rem_b > 0 and rem_a == 0

            if only_a_left or only_b_left:
                active = 'A' if only_a_left else 'B'
                active_is_me = (active == 'A') == is_algosia
                active_leading = (active == 'A' and balance == 1) or (active == 'B' and balance == -1)

                if active_is_me:
                    if sent >= n:
                        break
                    # C#1
                    bit = my_word[sent]
                    sent += 1
                    my_move = phase_c_move(bit, active_leading)
                else:
                    # C#2
                    my_move = 'N'

                opp_move = play_round(my_move)

                if not active_is_me:
                    # C#2
                    opp_word[received] = '0' if opp_move == 'N' else '1'
                    received += 1

                result = round_result(my_move, opp_move)
                if is_algosia:
                    balance += result
                else:
                    balance -= result
                continue

            # A/B
            sender = choose_sender(balance, rem_a, rem_b)
            sender_is_me = (sender == 'A') == is_algosia
            sender_leading = (sender == 'A' and balance == 1) or (sender == 'B' and balance == -1)

            # A/B
            base_move = sender_base_move(sender)
            one_move = sender_one_move(sender, sender_leading)

            if sender_is_me:
                # A/B#1
                bit = my_word[sent]
                sent += 1
                my_move = base_move if bit == '0' else one_move
            else:
                # A/B#2
                my_move = base_move

            opp_move = play_round(my_move)

            if not sender_is_me:
                # A/B#2
                opp_word[received] = '0' if opp_move == base_move else '1'
                received += 1

            result = round_result(my_move, opp_move)
            if is_algosia:
                balance += result
            else:
                balance -= result

        print('! ' + ''.join(opp_word), flush=True)


if __name__ == '__main__':
    main()