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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

string converter(string s, ll first, ll second) {
	string res = "";
	while(s.size() && s!="0") {
		string ns = "";
		ll reszta = 0;
		for(auto x : s) {
			int xx = x-'0';
			reszta = first*reszta + xx;
			ns.push_back((reszta/second) + '0');
			reszta %= second;
		}
		res.push_back(reszta + '0');
		s=ns;
		reverse(s.begin(), s.end());
		while(s.size() && s.back()=='0') s.pop_back();
		if(s.empty()) s.push_back('0');
		reverse(s.begin(), s.end());
	}
	while(res.size() && res.back()=='0') res.pop_back();
	if(res.empty()) res.push_back('0');
	reverse(res.begin(), res.end());
	return res;
}

int gn(int a, int b) {
	return rand() % (b-a+1) + a;
}

vector<int> gen_rand(int n, int x) {
	vector<int> v(n);
	for(auto &y : v) y=gn(0,x-1);
	return v;
}

vector<int> to_vec(string s) {
	int n = s.size();
	vector<int> v(n);
	for(int i=0; i<n; ++i) v[i] = (s[i] - '0');
	return v;
}

void Send(int x) {
	if(x==0) cout << "P\n";
	else if(x==1) cout << "K\n";
	else cout << "N\n";
	cout << flush;
}

int Receive() {
	char c; cin >> c;
	if(c=='P') return 0;
	if(c=='K') return 1;
	return 2;
}

int main() {
	srand(1676767);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	
	string kto; cin >> kto;
	bool user = 0;
	if(kto=="Bajtek") user = 1;

	int n, Z;
	cin >> n >> Z;
	while(Z--) {
		string s; cin >> s;
		string t = converter(s, 2, 3);
		vector<int> V = to_vec(t);
		int N = 3155;
		reverse(V.begin(), V.end());
		while(V.size() < N) V.push_back(0);
		reverse(V.begin(), V.end());
		vector<int> alg = gen_rand(N, 3);
		vector<int> bjt = gen_rand(N, 3);
		for(int i=0; i<N; ++i) V[i] = (V[i] + (user ? bjt[i] : alg[i]))%3;
		vector<int> res;
		for(int i=0; i<N; ++i) {
			Send(V[i]);
			int x = Receive();
			res.push_back(x);
			if(V[i] != x) {
				Send(x);
				Receive();
			}
		}
		for(int i=0; i<N; ++i) res[i] = (res[i] - (user ? alg[i] : bjt[i]) + 3) % 3;
		string ans = "";
		for(auto x : res) ans.push_back(x + '0');
		ans = converter(ans, 3, 2);
		reverse(ans.begin(), ans.end());
		while(ans.size() < n) ans.push_back('0');
		reverse(ans.begin(), ans.end());
		cout << "! " << ans << "\n";
		cout << flush;
	}

	return 0;
}