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

using ll = int64_t;



void answer(const string& str) {
  cout << "! " << str << endl;
}

int play_(int c) {
  static constexpr array<char, 3> moves{'P', 'K', 'N'};
  cout << moves[c] << endl;
  char response;
  cin >> response;
  return find(moves.begin(), moves.end(), response) - moves.begin();
}

int moveScore(int me, int oth) {
  if(me == oth) {
    return 0;
  }
  if((oth + 3 - me) % 3 == 1) {
    return 1;
  }
  return -1;
}

using u128 = __uint128_t;

void serializeBlock(vector<int>& ans, string& str, int l, int r) {
  u128 v = 0;
  v = 1;
  for(int i = l; i <= r; i++) {
    auto c = str[i];
    v *= 2;
    if(c == '1') {
      v++;
    }
  }

  vector<int> tmp(81);
  int rr = tmp.size() - 1;
  while(v) {
    tmp[rr--] = v % 3;
    v /= 3;
  }

  ans.insert(ans.end(), tmp.begin(), tmp.end());
}

vector<int> serialize(string str) {
  int blocks = (str.size() + 126) / 127;

  vector<int> ans;

  for(int b = 0; b < blocks; b++) {
    serializeBlock(ans, str, b * 127, min<int>(b * 127 + 126, str.size() - 1));
  }

  return ans;
}

void deserializeBlock(string& ans, vector<int>& vs, int l, int r) {
  u128 v = 0;
  for(int i = l; i <= r; i++) {
    v *= 3;
    v += vs[i];
  }

  vector<char> tmp(128, '0');
  int rr = tmp.size() - 1;
  while(v) {
    tmp[rr--] = '0' + v % 2;
    v /= 2;
  }

  bool one = false;
  for(auto c : tmp) {
    if(one) {
      ans.push_back(c);
    }
    if(c == '1') {
      one = true;
    }
  }
}

string deserialize(vector<int> vs) {
  int blocks = vs.size() / 81;
  string ans;
  for(int b = 0; b < blocks; b++) {
    deserializeBlock(ans, vs, b * 81, b * 81 + 80);
  }
  return ans;
}

struct Player {
  bool first;
  vector<int> message;

  int score = 0;
  vector<int> ans;
  int i = 0;

  bool prevBalance = false;
  int last = 0;
  int balances = 0;


  mt19937 ag{1234978452978};
  mt19937 bg{3468780264};

  void start(bool first_p, vector<int> message_p) {
    first = first_p;
    message = message_p;
    score = 0;
    ans.clear();
    i = 0;
    balances = 0;
  }

  bool ansReady() {
    return ans.size() == message.size();
  }

  int balance() {
    balances++;
    if(score == 1) {
      return 1;
    }
    return 0;
  }

  int run() {
    if(score != 0) {
      prevBalance = true;
      last = balance();
      
      
    }
    else {
      prevBalance = false;
      last = message[i++];      

      if(first) {
        last = (last + uniform_int_distribution<int>(0, 2)(ag)) % 3;
      }
      else {
        last = (last + uniform_int_distribution<int>(0, 2)(bg)) % 3;
      }
      
    }
    return last;
  }

  void apply(int oth) {
    score += moveScore(last, oth);

    if(!prevBalance) {
      if(first) {
        oth = (oth + 3 - uniform_int_distribution<int>(0, 2)(bg)) % 3;
      }
      else {
        oth = (oth + 3 - uniform_int_distribution<int>(0, 2)(ag)) % 3;
      }
    }
    

    

    if(!prevBalance) {
      ans.push_back(oth);
    }
  }
};

void game(string m1, string m2) {
  Player a;
  a.start(true, serialize(m1));
  Player b;
  b.start(false, serialize(m2));

  int rounds = 0;
  static int maxRounds = 0;

  static int lost = 0;
  static int total = 0;

  total++;

  while(true) {
    if(a.ansReady()) {
      assert(b.ansReady());

      auto ans1 = deserialize(a.ans);
      auto ans2 = deserialize(b.ans);
      assert(ans1 == m2);
      auto tmp = serialize(m2);
      assert(a.ans == tmp);
      tmp = serialize(m1);
      assert(b.ans == tmp);
      //assert(ans2 == m1);
      //assert(a.message == b.ans);
      maxRounds = max(maxRounds, rounds);
      if(rounds == maxRounds) {
       cout << "There was " << rounds << " rounds with " << a.balances << " balances " << " which is " << (double)a.balances / rounds << endl;
      }

      //cout << "There was " << rounds << " rounds max: " << maxRounds << endl;
      return;
    }

    int v1 = a.run();
    int v2 = b.run();
    a.apply(v2);
    b.apply(v1);
    rounds++;
  }
}

void test() {
  static mt19937 gen;
  int n = uniform_int_distribution<int>(1, 5000)(gen);
  string a;
  string b;
  for(int i = 0; i < n; i++) {
    a.push_back(uniform_int_distribution<int>(0, 1)(gen) + '0');
    b.push_back(uniform_int_distribution<int>(0, 1)(gen) + '0');
  }
  game(a, b);
}


void solve() {
  string name;
  cin >> name;

  int n, t;
  cin >> n >> t;

  Player player;

  vector<string> messages;


  for(int i = 0; i < t; i++) {
    string message;
    cin >> message;
    player.start(name == "Algosia", serialize(message));
    while(!player.ansReady()) {
      int ans = player.run();
      int got = play_(ans);
      player.apply(got);
    }
    answer(deserialize(player.ans));
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  //freopen("in", "r", stdin);
  solve();
  // for(int i = 0; i < 1000000; i++) {
  //  test();
  // }
}