#include <bits/stdc++.h>
using namespace std;
struct B{static const uint32_t M=1000000000u;vector<uint32_t>a;B(uint64_t v=0){*this=v;}B&operator=(uint64_t v){a.clear();if(!v)return *this;while(v){a.push_back(v%M);v/=M;}return *this;}bool z()const{return a.empty();}void t(){while(!a.empty()&&a.back()==0)a.pop_back();}static B f(const string&s){B x;for(char c:s){x.x();if(c=='1')x.s(1);}return x;}string g(int n)const{B x=*this;string r(n,'0');for(int i=n-1;i>=0;--i){if(!x.z()&&(x.a[0]&1u))r[i]='1';x.y();}return r;}static int c(const B&x,const B&y){if(x.a.size()!=y.a.size())return x.a.size()<y.a.size()?-1:1;for(int i=(int)x.a.size()-1;i>=0;--i)if(x.a[i]!=y.a[i])return x.a[i]<y.a[i]?-1:1;return 0;}
bool operator<(const B&o)const{return c(*this,o)<0;}bool operator==(const B&o)const{return c(*this,o)==0;}bool operator!=(const B&o)const{return c(*this,o)!=0;}bool operator>(const B&o)const{return c(*this,o)>0;} bool operator<=(const B&o)const{return c(*this,o)<=0;}bool operator>=(const B&o)const{return c(*this,o)>=0;}void s(uint32_t v){uint64_t k=v;size_t i=0;while(k){if(i==a.size())a.push_back(0);uint64_t u=(uint64_t)a[i]+k;a[i]=u%M;k=u/M;++i;}}void x(){uint64_t k=0;for(size_t i=0;i<a.size();++i){uint64_t u=2ull*a[i]+k;a[i]=u%M;k=u/M;}if(k)a.push_back(k);}void y(){uint64_t r=0;for(int i=(int)a.size()-1;i>=0;--i){uint64_t u=a[i]+r*M;a[i]=u/2;r=u%2;}t();}
 friend B operator+(const B&x,const B&y){B r;r.a.resize(max(x.a.size(),y.a.size()));uint64_t k=0;for(size_t i=0;i<r.a.size();++i){uint64_t u=k;if(i<x.a.size())u+=x.a[i];if(i<y.a.size())u+=y.a[i];r.a[i]=u%M;k=u/M;}if(k)r.a.push_back(k);return r;}
 friend B operator-(const B&x,const B&y){B r=x;int64_t k=0;for(size_t i=0;i<y.a.size()||k;++i){int64_t u=(int64_t)r.a[i]-(i<y.a.size()?y.a[i]:0)-k;if(u<0){u+=M;k=1;}else k=0;r.a[i]=u;}r.t();return r;}
 friend B operator*(const B&x,uint32_t m){if(x.z()||!m)return B(0);B r;r.a.resize(x.a.size());uint64_t k=0;for(size_t i=0;i<x.a.size();++i){uint64_t u=(uint64_t)x.a[i]*m+k;r.a[i]=u%M;k=u/M;}while(k){r.a.push_back(k%M);k/=M;}return r;}
 B d(uint32_t m,uint32_t*o=0)const{B r;r.a.resize(a.size());uint64_t k=0;for(int i=(int)a.size()-1;i>=0;--i){uint64_t u=a[i]+k*M;r.a[i]=u/m;k=u%m;}r.t();if(o)*o=k;return r;}
};struct R{B l,s;};struct T{B p,k,n;};struct U{B p,n;};B P(int n){B x(1);for(int i=0;i<n;++i)x.x();return x;}T A(const B&s){T r;r.p=(s+B(2)).d(3);r.k=(s+B(1)).d(3);r.n=s-r.p-r.k;return r;}U C(const B&s){U r;r.p=s.d(4);r.n=s-r.p;return r;}
pair<char,R>D(const R&r,const B&x){T t=A(r.s);B o=x-r.l;if(o<t.p)return{'P',{r.l,t.p}};if(o<t.p+t.k)return{'K',{r.l+t.p,t.k}};return{'N',{r.l+t.p+t.k,t.n}};}R E(const R&r,char c){T t=A(r.s);if(c=='P')return{r.l,t.p};if(c=='K')return{r.l+t.p,t.k};return{r.l+t.p+t.k,t.n};}pair<char,R>F(const R&r,const B&x){U t=C(r.s);B o=x-r.l;if(o<t.p)return{'P',{r.l,t.p}};return{'N',{r.l+t.p,t.n}};}R G(const R&r,char c){U t=C(r.s);if(c=='P')return{r.l,t.p};return{r.l+t.p,t.n};}int H(char a,char b){if(a==b)return 0;if(a=='P'&&b=='K'||a=='K'&&b=='N'||a=='N'&&b=='P')return 1;return -1;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string w;int n,t;cin>>w>>n>>t;bool a=w=="Algosia";while(t--){string s;cin>>s;B x=B::f(s);R m{B(0),P(n)},o{B(0),P(n)};int d=0;while(!(m.s==B(1)&&o.s==B(1))){char c;R y=m;if(!d){auto p=D(m,x);c=p.first;y=p.second;}else{bool l=d==1,u=a?l:!l;if(u)c='P';else{auto p=F(m,x);c=p.first;y=p.second;}}cout<<c<<'\n';cout.flush();char e;if(!(cin>>e))return 0;m=y;if(!d)o=E(o,e);else{bool l=d==1,u=a?l:!l,v=!u;if(!v)o=G(o,e);}   char p=a?c:e,q=a?e:c;d+=H(p,q);if(abs(d)>1)return 0;}cout<<"! "<<o.l.g(n)<<'\n';cout.flush();}return 0;}