//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
using i128=__int128_t;
void die(string S){puts(S.c_str());exit(0);}
mt19937_64 rng(114514);
string cha="KPN";
const int P=100,Q=76;
const string sP="1100100";
int id[256];
int game(char my,char op)
{
	int a=id[my];
	int b=id[op];
	if(a==b) return 0;
	if(a==(b+1)%3) return 1;
	return -1;
}
int Mod(string a,int b)
{
	int ans=0;
	for(auto ch:a)
		ans=(ans*2+(ch^48))%b;
	return ans;
}
string Div(string a,int b)
{
	string ans;
	int rem=0;
	for(auto ch:a)
	{
		rem=(rem*2+(ch^48));
		ans+=(char)(48^(rem/b));
		rem%=b;
	}
	rev(ans);
	while(sz(ans)&&ans.back()=='0') ans.pop_back();
	rev(ans);
	return ans;
}
int Comp(string a,string b)
{
	if(sz(a)!=sz(b)) return (sz(a)<sz(b))?(-1):(1);
	if(a!=b) return (a<b)?(-1):(1);
	return 0;
}
string Mul(string a,int b)
{
	rev(a);
	int rem=0;
	string ans;
	for(auto ch:a)
	{
		rem+=(ch^48)*b;
		ans+=(char)(48^(rem&1));
		rem>>=1;
	}
	while(rem)
	{
		ans+=(char)(48^(rem&1));
		rem>>=1;
	}
	while(sz(ans)&&ans.back()=='0') ans.pop_back();
	rev(ans);
	return ans;
}
string Add(string a,int b)
{
	rev(a);
	int rem=b;
	string ans;
	for(auto ch:a)
	{
		rem+=(ch^48);
		ans+=(char)(48^(rem&1));
		rem>>=1;
	}
	while(rem)
	{
		ans+=(char)(48^(rem&1));
		rem>>=1;
	}
	while(sz(ans)&&ans.back()=='0') ans.pop_back();
	rev(ans);
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i=0;i<3;i++) id[cha[i]]=i;
	string player;
	cin>>player;
	int n,t;
	cin>>n>>t;
	while(t--)
	{
		string number;
		cin>>number;
		vector<int> rv(n*2);
		for(auto &x:rv) x=rng()%2;
		if(player[0]=='A')
			for(int i=0;i<n;i++)
				number[i]^=rv[i];
		else
			for(int i=0;i<n;i++)
				number[i]^=rv[n+i];
		string Max0(n,'1'),Max1(n,'1');
		int win=0;
		vector<pii> seq;
		while(sz(Max0)||sz(Max1))
		{
			if(!win)
			{
				char send=cha[Mod(number,3)%3];
				cout<<send<<endl;
				char recv;
				cin>>recv;
				win+=game(send,recv);
				seq.pb(id[recv]%3,3);
				number=Div(number,3);
				Max0=Div(Max0,3);
				Max1=Div(Max1,3);
			}
			else
			{
				int cmp=Comp(Max0,Max1);
				if(cmp<0||(!cmp&&player[0]=='A'))
				{
					if(Comp(Max1,sP)<=0)
					{
						int start=(win>0)?(0):(2);
						char send=cha[0];
						cout<<send<<endl;
						char recv;
						cin>>recv;
						win+=game(send,recv);
						seq.pb((id[recv]+3-start)%3,2);
						Max1=Div(Max1,2);
					}
					else
					{
						char send=cha[0];
						cout<<send<<endl;
						char recv;
						cin>>recv;
						win+=game(send,recv);
						if(send==recv)
						{
							seq.pb(-1,0);
							Max1=Add(Div(Max1,P),1);
							Max1=Mul(Max1,P-Q);
						}
						else
						{
							seq.pb(-1,1);
							Max1=Add(Div(Max1,P),1);
							Max1=Mul(Max1,Q);
						}
					}
				}
				else
				{
					if(Comp(Max0,sP)<=0)
					{
						int start=(win>0)?(2):(0);
						char send=cha[(start+Mod(number,2))%3];
						cout<<send<<endl;
						char recv;
						cin>>recv;
						win+=game(send,recv);
						number=Div(number,2);
						Max0=Div(Max0,2);
					}
					else
					{
						int start=(win>0)?(2):(0);
						int rem=Mod(number,P);
						int tp=(rem<Q)?(1):(0);
						if(start) tp^=1;
						int val=(rem<Q)?(Q):(P-Q);
						int nrem=(rem<Q)?(rem):(rem-Q);
						char send=cha[(start+tp)%3];
						cout<<send<<endl;
						char recv;
						cin>>recv;
						win+=game(send,recv);
						number=Div(number,P);
						number=Mul(number,val);
						number=Add(number,nrem);
						Max0=Add(Div(Max0,P),1);
						Max0=Mul(Max0,val);
					}
				}
			}
		}
		string Answer;
		rev(seq);
		for(auto [a,b]:seq)
			if(~a)
			{
				Answer=Mul(Answer,b);
				Answer=Add(Answer,a);
			}
			else if(b)
			{
				int rem=Mod(Answer,Q);
				Answer=Add(Mul(Div(Answer,Q),P),rem);
			}
			else
			{
				int rem=Mod(Answer,P-Q);
				Answer=Add(Mul(Div(Answer,P-Q),P),rem+Q);
			}
		Answer=string(n-sz(Answer),'0')+Answer;
		if(player[0]=='A')
			for(int i=0;i<n;i++)
				Answer[i]^=rv[n+i];
		else
			for(int i=0;i<n;i++)
				Answer[i]^=rv[i];
		cout<<"! "<<Answer<<endl;
	}
	return 0;
}