#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using ull = uint64_t;
using ll = int64_t;

struct TreNum {
  vector<ull> digits;
  int n, len;
  ull pow39 = 1;
  TreNum(int _n) {
    len = ((n = _n) + 38) / 39;
    digits.resize(len);
    for(int i = 1; i <= 39; i++) {
      pow39 *= 3;
    }
  }
  void mul2() {
    ull carry = 0;
    for(int i = 0; i < len; i++) {
      digits[i] *= 2;
      digits[i] += carry;
      carry = (digits[i] / pow39);
      digits[i] -= carry * pow39;
    }
  }
  void add1() {
    ull carry = 1;
    for(int i = 0; i < len; i++) {
      digits[i] += carry;
      carry = (digits[i] / pow39);
      digits[i] -= carry * pow39;
      if(!carry) break;
    }
  }
  string to_tre() {
    string res = "";
    for(int i = 0; i < len; i++) {
      ull num = digits[i];
      for(int b = 0; b <= 38; b++) {
        if(i * 39 + b + 1 > n) break;
        res += ('0' + num % 3);
        num /= 3;
      }
    }
    reverse(all(res));
    return res;
  }
};

struct BitNum {
  vector<ull> bits;
  int n, len;
  BitNum(int _n) {
    len = ((n = _n) + 63) / 64;
    bits.resize(len);
  }
  BitNum mul2() {
    BitNum res(*this);
    int old_bit = 0;
    for(int i = 0; i < len; i++) {
      int new_carry = !!(bits[i] & (ull(1) << ull(63)));
      res.bits[i] = (bits[i] << 1) | old_bit;
      old_bit = new_carry;
    }
    return res;
  }
  void add(BitNum const& other) {
    ull carry = 0;
    for(int i = 0; i < len; i++) {
      ull b = bits[i];
      bits[i] = bits[i] + other.bits[i] + carry;
      if((carry && numeric_limits<ull>::max() - other.bits[i] <= b)
                || numeric_limits<ull>::max() - other.bits[i] < b) {
        carry = 1;
      }
      else {
        carry = 0;
      }
    }
  }
  void mul3() {
    auto r = this->mul2();
    r.add(*this);
    this->bits = move(r.bits);
  }
  string to_string() {
    string res = "";
    for(int i = 0; i < n; i++) {
      res += '0' + !!(bits[i / 64] & (ull(1) << ull(i % 64)));
    }
    reverse(all(res));
    return res;
  }
};

string tre_to_bin(int n, int m, string const& tr) {
  BitNum bit(n);
  BitNum off1(n); off1.bits[0] = 1;
  BitNum off2(n); off2.bits[0] = 2;
  
  for(int i = 0; i < m; i++) {
    bit.mul3();
    if(tr[i] == '1') bit.add(off1);
    else if(tr[i] == '2') bit.add(off2);
    // assert(to_bin.substr(0, len) == bi.substr(0, len));
  }
  
  return bit.to_string();
}

string bin_to_tre(int n, int m, string const& bi) {
  TreNum num(m);

  for(int i = 0; i < n; i++) {
    num.mul2();
    if(bi[i] == '1') num.add1();
  }

  return num.to_tre();
}

const string magic[] = {
  "00110010111001000001000101001010110011100100010101001111001101000011011010001111010010110011011100000011100101000001100000110010011001011010101010101111111000110111001100110101011111011011111010101100101110101001011001001100011011001000001011110100101001110111010110011110111011111111101101100100101011010011001110101010110100111100011011011010110011100101011100111000101001001011111110111110100001001111010000100101010010010001101010111100101111001110101001101010000110001010100111000101001110110011111101110100000101100101100011110101100010101010011101000101111100010000101111100000001100101100110010011000000001101111110110011000011110111010011110100011110010111111010001101011111111111101111101110101100101101101101011011001010010010001110101000010001110001101010100111101110111011011111001110010110011100000011010000110101101110011111110110110000010110001110110010101010000111000011111110011100000000100000111110001101111001101001100001000110010011001100101000001100110101110010000110011001010100011000001110100011101100000101100010111010100000010000010010110010100000000111011100010100110111001000000010010000111101100110100101111110110111011101111010100100000110111111001101100011111001010010001000110111100000111101111010101011000100000100101010111011110110010000011010000111001010011001000101110000110101001000010100010000010011110011110101010111011010101001100101111000001100001001100001011000001011101101000111011011111100111000111011011010110001011111001001110001010011100111001001010010100100101010100011001101110101000110010100011001010010111101110101100101001001000011111000011101100110101100001110100010111100101010001001100111111010111110011000001011011101110100001110011101101001001001000111010000110001110001100110000110111001000000001111100000010000100001100011010100100100101000000110100101110011110101110000111011001000100110100111111101001101101111001111010110010010010010010111000100111101101010000111110100110100001101110001101000011100001101001101110101100001110001010100010011010001110110111010011011100000000001111010101101011100010101000110010001101110111001011101111111101010100100110101110101110001100101001000100001000001110101010010110000010100010010010100010101011111110011000001100011111010101101111010011100101111110100001100101000101101001010011110010111110010100011110010010000001011011010010101001011101101011110000010100000011101100010000110101001010101001001000010100111101100101101011010100010001011100001000000101001101110111100010101111011111101111000000100001101010101011110101001010000101111100000001101011101010101111001100001001110000100101111110110110111111100010001111010011001011110110001011110010000011001100111101100011100011110100100010011001010010001000111011100101110101110100011101111010001100111001010001010101111011001100111101111010111010001011100100001110011011101111111110011110001100100001010011101010001010011100011110111010011110111101001101001001100110101000100100010010101010111101001000110111000001010000011011110010010011001010010000101101011111011100000111110111011011000101111111011001101010011001000001000001111110011111111100011110101000001110110101110000011100111111010100100011001110110110100001101101001101001111111011001110001101000100100100011000110100000101000001000011000111011110100101100010011111011101110100100111010100100101001111000011011111100010111011010001001111111000111000000111001011011110110001001000101001111100001001110100010101101011100101010001011101100111101001110010001101000101010100110001000000110011010111100011011111010000010000011100100011110111101111011100111011000101111011110000010110111111011101101011001001100001110011001001111100011100111110111110111000111110001110110110001000111100001100010011110100110111110010101000010011110000001101010000110010010100110010101011011100001110110011110010100000001111000010010111001000010011010001000000011000011000100010010011010111011110000100011011110110100000000010111110010110000010101011111100101011101011100101010010000011011111000101111010111001000000011100111010011110110100111100010101010111001100001100101100010011100010000111100101001110111111011011100010110001111000111101010101001011101111011111000011000011100000111101011011111000111011111111101100110010111010110001000100100100101010001011101100001000101000001001110011111100010010110010111011001011001100001011111110111011111010000011000111011011110001111000010101100001111011110111010111111010110010111011000000110110001011010010111000111111011110001101001110110000101111011000010111001011010111000100101111110111000000101111111011011110100000001110011111111000110001110010000011010000111101100101001101010011111100100010111111110001110110111100001000011001100101111000111011011001000110011000010110101011011111010001001110100000000010101110001001111100010000000000101001011010100000010011100011011001010001111011111101000100011110111010110001011100100101100001110111100011000110111010001101100010011100101000010001110001010100010100000101001011001010100000101111010111101000011100110110",
  "01100000110010000000001100000110010001101111000001101100101111100101101010000100000111011000100101101000110000111010001010110111110110000010001100111111011000000000010000100101011001101111000011010000111001010010110100011110100110100000100010001101000100110111100000000111101010111100011100101110001011110011100100110000110111010100100111010101000000011011011010010001100001101101101010101010011000100000111011011010111011110001110001111000110101001010000110111101100111011100111001100010101001001000011010111111000100110010010100001101111101000010101000110101101100010010101011110010011001110010010001010010101100000001011010110001011100111101001111000111111100111101110000011101100110000100111011101010010011111001110001111110100101011001011111110101011000101101010101000101111011010000111000011011101011001100001100110100000101111000011010000011111101011110100100011010100000011110101001010010010111010100000111010111101011101111010011110001001010111100010001100010110001110111011001001010100100000101110100111000101001011010100100101000010110000111010001010011101100000111110010110100100010001010010000010110011110110011110000011011101111111101101101111011000101011010101100000101000000001010110000110011100010000000011001111011110000010101010011101000010000101000111011110100011100000111110000111101001100111010100101100000110100001000100110010000101010111001011010000101001001011111010010101111001000101011001110111110010000000000001100011111110011110101001110110110101100100011010011010101011000000101000100010011001111101011100000110110010100110001001101100011000111100101100110001110100101110010001100000000000000010110000101100010000011011000010001010011011101011111100010101001000100000111011011010001011100100110001111111111101000100011111100011011101100011101001010110000001011100001011001001011100000110011110010001000001011110000010001000100001101000110100001011000100001101110001100011101001000011111111000111100010111011100001010111101111111000011101100100000101010010100001111000111100111100110101110100010100100100110111111010101001110011101001100000000101000011010111100011110100110010001010100000111000001010101111001000110000111100110000011010011110100101000111111101101001010111011001111101111100100100010101000001011010001010100100000100101101111110111111100101111100110001010001000010001011000001101011001110100110110000100111110111000100000010001010101000011110000111101000110011011001110111101001101110101111100011110011101111001001101000110100101100111001001011000111101111111111011000000101110010010101111001010001100100011011111110011010111110111100011000000110011110110111111000011011100101111000000111011001101111110111111011011110010010011110001100000110011010010110110010110001100100101001000111101100100010111001010000000001010110010001100011001111010110110111011000110001110000110001101111011111010111001101110010010001101100000011110111010111000101101101100101100111011011110001011011001100010101011101001000101001111110010101000010000110110111011100011000100110111011000010000010100111110101011111111100011100110101101011111010100000100101111001101010111100000110001100001101000000100110111111101100110000010111010001101001010101101010100001000101111001101111001100110100111111111010010100100010100010100001110101100010110110000111111101100011100100111000010110010111000111101101110100100001001101001101011010010000100010011011001100110110101110100000000111110110111101010000010001110101010011100011010100101010000010011000101101111100011101011000010101011010101111101100011101001011100011111100000110000011011011000110100101110011001101011111100011011110001100000110011110111100111000101100111010010110110100101011111001111001100000001111000010110010101100001111000001111100011011110111111100001110001011011100100010011100100011101110000001111011111001110101101000101100110010110000110110110100000000000011001111101111110110011101011010010011011101100100111110110000100110100001100101101100111011010010100110110100110010011100111111101111111110100001001100110110101110100100000000011110110110010111001010100011101010001101111010011111000001111011101011111110011000111000100110000110000101101010000111100100011101001101111100101111111010011101001101000100000011110011011011100011011110111001010011001011110101101011100111001100000010011000101110001000110100110010000101110011010011011100100011011001011010111111110001111110100100000100100011100011100111101100010001010111001001111000000101000000100110010101110011100001110011001101011111101010100101100000011010110001011000101100011111100000011010010011100110100110111110111100000111101111111100011101000100110010001110110100110010101111000011100001000001111111110001101011011111011011100011111111101000011010110101110011011111101011110111000010011110110110011111111101010100001011110100101010111101001101111101010111111011101111100101001100011010111110011111010010100011110110001000010010110111111101001011010100111000100000001001000010010110101100111011100110001000000011111110111010001101000110111110000111101"
};

void xor_with(string& b1, string const& b2) {
  for(int i = 0; i < (int) b1.size(); i++) {
    if(b1[i] == b2[i]) b1[i] = '0';
    else b1[i] = '1';
  }
}

const char MOVE_WHEN_LOSING = 'P';
const char MOVE_WHEN_WINNING = 'K';

int move_to_num(char c) {
  if(c == 'P') return 0;
  if(c == 'K') return 1;
  if(c == 'N') return 2;
  assert(0);
  return 2137;
}

char winning(char c) {
  if(c == 'P') return 'N';
  if(c == 'K') return 'P';
  if(c == 'N') return 'K';
  assert(0);
  return 'n';
}

string solve(int who, int n, int m) {
  string bin; cin >> bin;
  xor_with(bin, magic[who]);

  // cerr << "magicked: " << bin << '\n';

  string tre_to_send = bin_to_tre(n, m, bin);
  string tre_recieved = "";
  // cerr << tre_to_send << '\n';

  for(int i = 0; i < m; i++) {
    char move;
    char d = tre_to_send[i];
    move = (d == '0' ? 'P' : (d == '1' ? 'K' : 'N'));
    cout << move << '\n';
    cout.flush();
    string response; cin >> response;
    int losing = 0;

    if(response[0] == winning(move)) losing = 1;
    else if (winning(response[0]) == move) losing = -1;
    tre_recieved += ('0' + move_to_num(response[0]));

    if(losing != 0 && i != (m - 1)) {
      if(losing == 1) {
        // cerr << "Przegrywam, więc gram. " << MOVE_WHEN_LOSING << '\n';
        move = MOVE_WHEN_LOSING;
      }
      else {
        // cerr << "Wygrywam, więc gram. " << MOVE_WHEN_WINNING << '\n';
        move = MOVE_WHEN_WINNING;
      }
      cout << move << '\n';
      cout.flush();
      losing = 0;
      char resp; cin >> resp;
    }
  }

  string res_str = tre_to_bin(n, m, tre_recieved);
  // cerr << "Magicked_other: " << res_str << '\n';
  xor_with(res_str, magic[who ^ 1]);
  // cerr << "UNMagicked_other: " << res_str << '\n';

  return res_str;
}

int main() {
  string name; cin >> name;
  int n, t; cin >> n >> t;
  int m = int(ceil(n / log2(3) + 2));

  int who = (name == "Algosia" ? 0 : 1);

  for(int tc = 1; tc <= t; tc++) {
    auto res = solve(who, n, m);
    cout << "! " << res << '\n';
    cout.flush();
  }

}