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
151
152
153
#include <bits/stdc++.h>                                                                                                                                                                                                                                                                                                                                                                                                                            
#define rep(i, p, k) for (int i = (p); i < (k); ++i)                                                                                                                                                                                                                                                                                                                                                                                                
using namespace std;                                                                                                                                                                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                                                                                                                                                    
string name;                                                                                                                                                                                                                                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                                                                                                                                                    
#define debug(x)                                                               \                                                                                                                                                                                                                                                                                                                                                                    
  do {                                                                         \                                                                                                                                                                                                                                                                                                                                                                    
    stringstream ss;                                                           \                                                                                                                                                                                                                                                                                                                                                                    
    ss << name << ": " << #x << " = " << x << '\n';                            \                                                                                                                                                                                                                                                                                                                                                                    
    cerr << ss.str();                                                          \                                                                                                                                                                                                                                                                                                                                                                    
  } while (0);                                                                                                                                                                                                                                                                                                                                                                                                                                      
                                                                                                                                                                                                                                                                                                                                                                                                                                                    
void solve(int n, string const &t, string &r) {                                                                                                                                                                                                                                                                                                                                                                                                     
  int move_cnt = 0;                                                                                                                                                                                                                                                                                                                                                                                                                                 
  // debug(t);                                                                                                                                                                                                                                                                                                                                                                                                                                      
  int me = 0, other = 0, state = 0;                                                                                                                                                                                                                                                                                                                                                                                                                 
  auto get_3_move = [&] {                                                                                                                                                                                                                                                                                                                                                                                                                           
    if (other == n)                                                                                                                                                                                                                                                                                                                                                                                                                                 
      return 'K';                                                                                                                                                                                                                                                                                                                                                                                                                                   
    if (t[other++] == '1')                                                                                                                                                                                                                                                                                                                                                                                                                          
      return 'N';                                                                                                                                                                                                                                                                                                                                                                                                                                   
    if (other == n)                                                                                                                                                                                                                                                                                                                                                                                                                                 
      return 'P';                                                                                                                                                                                                                                                                                                                                                                                                                                   
    return t[other++] == '0' ? 'P' : 'K';                                                                                                                                                                                                                                                                                                                                                                                                           
  };                                                                                                                                                                                                                                                                                                                                                                                                                                                
  auto parse_3_move = [&](char z) {                                                                                                                                                                                                                                                                                                                                                                                                                 
    if (me == n)                                                                                                                                                                                                                                                                                                                                                                                                                                    
      return;                                                                                                                                                                                                                                                                                                                                                                                                                                       
    if (z == 'N') {                                                                                                                                                                                                                                                                                                                                                                                                                                 
      r += '1';                                                                                                                                                                                                                                                                                                                                                                                                                                     
      me++;                                                                                                                                                                                                                                                                                                                                                                                                                                         
      return;                                                                                                                                                                                                                                                                                                                                                                                                                                       
    }                                                                                                                                                                                                                                                                                                                                                                                                                                               
    r += '0';                                                                                                                                                                                                                                                                                                                                                                                                                                       
    me++;                                                                                                                                                                                                                                                                                                                                                                                                                                           
    if (me == n)                                                                                                                                                                                                                                                                                                                                                                                                                                    
      return;                                                                                                                                                                                                                                                                                                                                                                                                                                       
    if (z == 'P') {                                                                                                                                                                                                                                                                                                                                                                                                                                 
      r += '0';                                                                                                                                                                                                                                                                                                                                                                                                                                     
    }                                                                                                                                                                                                                                                                                                                                                                                                                                               
    if (z == 'K') {                                                                                                                                                                                                                                                                                                                                                                                                                                 
      r += '1';                                                                                                                                                                                                                                                                                                                                                                                                                                     
    }                                                                                                                                                                                                                                                                                                                                                                                                                                               
    me++;                                                                                                                                                                                                                                                                                                                                                                                                                                           
  };                                                                                                                                                                                                                                                                                                                                                                                                                                                
  auto get_2_move = [&] {                                                                                                                                                                                                                                                                                                                                                                                                                           
    if (other == n)                                                                                                                                                                                                                                                                                                                                                                                                                                 
      return 'N';                                                                                                                                                                                                                                                                                                                                                                                                                                   
    return t[other++] == '0' ? 'P' : 'N';                                                                                                                                                                                                                                                                                                                                                                                                           
  };                                                                                                                                                                                                                                                                                                                                                                                                                                                
  auto parse_2_move = [&](char z) {};                                                                        
  auto get_1_move = [&] { return 'P'; };                                                                     
  auto parse_1_move = [&](char z) {                                                                          
    if (me == n)                                                                                             
      return;                                                                                                
    if (z == 'P')                                                                                            
      r += '0';                                                                                              
    if (z == 'N')                                                                                            
      r += '1';                                                                                              
    me++;                                                                                                    
  };                                                                                                     
  auto update_score = [&](char a, char b) {
    if (a == b)
      return;
    if (a == 'P' && b == 'K')
      state++;
    if (a == 'P' && b == 'N')
      state--;
    if (a == 'K' && b == 'N')
      state++;
    if (a == 'K' && b == 'P')
      state--;
    if (a == 'N' && b == 'P')
      state++;
    if (a == 'N' && b == 'K')
      state--;
  };
  int count_after = -1;
  int todo = 0;
  while (me < n || other < n) {
    if(me == n || other == n) {
      if(count_after == -1) {
        count_after = 0;
        todo = n - me + n - other;
      }
      count_after++;
    }
    // debug(me);
    // debug(other);
    // debug(state);
    // debug(move_cnt);
    // debug(me);
    // debug(other);
    // debug(n);
    // debug(state);
    move_cnt++;
    // debug(r);
    char me_move, other_move;
    auto inter = [&] {
      cout << me_move << endl;
      cin >> other_move;
    };
    switch (state) {
    case -1: {
      me_move = get_2_move();
      inter();
      parse_2_move(other_move);
      break;
    }
    case 0: {
      me_move = get_3_move();
      inter();
      parse_3_move(other_move);
      break;
    }
    case 1: {
      me_move = get_1_move();
      inter();
      parse_1_move(other_move);
      break;
    }
    }
    update_score(me_move, other_move);
    // debug(me_move);
    // debug(other_move);
    // debug("\nNEXT TURN\n");
    // sleep(2);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> name;
  // debug(name);
  mt19937 gen(0xbeeeeeeeee);
  int n, q;
  cin >> n >> q;
  vector<int> a_bits(n), b_bits(n);
  for (auto &v : a_bits)
    v = gen() % 2;
  for (auto &v : b_bits)
    v = gen() % 2;
  string s, r;
  while (q--) {
    cin >> s;
    r.clear();
    rep(i, 0, n) s[i] ^= (name[0] == 'A' ? a_bits : b_bits)[i];
    solve(n, s, r);
    rep(i, 0, n) r[i] ^= (name[0] == 'A' ? b_bits : a_bits)[i];
    cout << "! " << r << endl;
  }
}