#include<iostream>
#include<random>
#include<chrono>
using namespace std;
constexpr long long MAXUNS=(1ll<<32)-1;
unsigned long long MLAST;
 int N,R;
 struct mint{
     unsigned tab[160]={0};
     mint operator+(const mint& r){
         mint zw;long long tmp=0;
         for(int j=0;j<N;j++)
         {
            tmp+=tab[j];tmp+=r.tab[j];
            zw.tab[j]=(tmp&((1ll<<32)-1));
            tmp=(tmp>>32);
         }
         return zw;
     }
     mint operator-(const mint& r){
         mint zw;long long tmp=0;
         for(int j=0;j<N;j++)
         {
             tmp+=tab[j];tmp-=r.tab[j];
             if(tmp<0){zw.tab[j]=tmp+(1ll<<32);tmp=-1;}
             else {zw.tab[j]=tmp;tmp=0;}
         }
         return zw;
     }
         mint operator+(unsigned x){
             mint zw; long long tmp=x;
             for(int j=0;j<N;j++)
             {
                 tmp+=tab[j];
                 zw.tab[j]=(tmp&MAXUNS);
                 tmp=(tmp>>32);
             }
             return zw;
         }
         mint operator/(unsigned x){
             mint zw;long long tmp=0;
             for(int j=N-1;j>=0;j--)
             {
                 zw.tab[j]=(tmp+tab[j])/x;
                 tmp=(tmp+tab[j])%x;
                 tmp*=(1ll<<32);
             }
             return zw;
         }
         void operator^=(const mint& r){
             for(int j=0;j<N;j++){tab[j]^=r.tab[j];}
         }
         bool operator<=(const mint& r)const{
             for(int j=N-1;j>=0;j--){if(tab[j]==r.tab[j]) continue;return tab[j]<r.tab[j];}
             return 1;
         }
         bool operator==(const mint& r)const{
             for(int j=0;j<N;j++) if(tab[j]!=r.tab[j]) return 0;return 1;
         }
        // void wypisz(){for(int j=0;j<N;j++){for(int z=0;z<(min(32,R*(j==N-1 && R!=0)));z++)cout<<((tab[j]>>z)&1);}}
         string wypisz(){string zw; for(int j=0;j<N;j++){for(int z=0;z<((R==0 || j!=N-1)?32:R);z++)zw+=('0'+((tab[j]>>z)&1));}return zw;}
 };
char nacyfre[128];
int naznak[3];
unsigned seed[2]={232343441,348342342};
void inicjuj(){
nacyfre['P']=0;
nacyfre['N']=1;
nacyfre['K']=2;
naznak[0]='P';
naznak[1]='N';
naznak[2]='K';
}

mint ZERO,MAKS;
int zmien(char ostatni,char zwrot)
 {
    int zmiana=(nacyfre[ostatni]-nacyfre[zwrot]+3)%3;
       if(zmiana==2) return -1;
       if(zmiana==1) return 1;
       return 0;
 }
 mint wygeneruj(mt19937& gen)
 {
     mint zw;
     for(int j=0;j<N;j++)zw.tab[j]=gen();
    if(R!=0) zw.tab[N-1]=zw.tab[N-1]%MLAST;
    return zw;
 }



class Osoba
{
    mt19937 gen,gen2;
    mint dane;
    mint xor_,dexor;
    mint lo,hi,ichlo,ichhi;
    char ostatni;
    int wynik=0;
    bool odgadlismy=0,onodgadl=0;
    public:
    void Init(mint dane_, bool osoba)
    {
        gen.seed(seed[osoba]);
        gen2.seed(seed[1-osoba]);
        xor_=wygeneruj(gen);
        dexor=wygeneruj(gen2);
        dane=dane_;
        dane^=xor_;
        lo=ZERO;hi=MAKS;ichlo=ZERO;ichhi=MAKS;
    }
    char zagraj()
    {
        if((onodgadl && wynik!=0) || (wynik==1 && !odgadlismy))
        {
           ostatni='P'; return 'P';
        }
       else if(wynik==0)
        {
            mint trid=(ichhi-ichlo)/3;
            mint tridp1=trid+1;
            mint przed=ichlo+trid;
            if(dane<=przed){
                ichhi=przed;
                ostatni='P';return ostatni;
            }
            else if(dane<=przed+tridp1){
                ichlo=przed+1;ichhi=przed+tridp1;
                ostatni= 'N';return ostatni;
            }
            else {ichlo=przed+tridp1+1;
            ostatni='K';return ostatni;}
        }
        else
        {
         mint pmid=(ichhi-ichlo)/4;
         if(dane<=ichlo+pmid){
                ichhi=ichlo+pmid;
           ostatni='P';return 'P';//remis
         }
         else {
             ichlo=ichlo+pmid+1;
                if(wynik==1) {ostatni='K';return 'K';}
                else {ostatni='N';return 'N';}
         }
        }
    }
    bool zwrotna(char zwrot)
    {
        if((odgadlismy && wynik!=0) || (wynik==-1 && !onodgadl))
        {

        }
        else if(wynik==0)
        {
            mint trid=(hi-lo)/3;
            mint tridp1=trid+1;
            mint przed=lo+trid;
             if(zwrot=='P'){hi=przed;}
             if(zwrot=='N'){lo=przed+1;hi=przed+tridp1;}
             if(zwrot=='K'){lo=przed+tridp1+1;}
        }
        else
        {
         mint pmid=(hi-lo)/4;
         if(zwrot=='P') hi=lo+pmid;
         if(zwrot=='K' || zwrot=='N') lo=lo+pmid+1;
        }
        wynik+=zmien(ostatni,zwrot);

       if(hi<=lo) odgadlismy=1;
       if(ichhi<=ichlo) onodgadl=1;
       return (odgadlismy && onodgadl);
    }
    mint wypisz()
    {
        lo^=dexor;
        return lo;
    }
}Alicja[50];

int main(){
    ios_base::sync_with_stdio(0);

    string kto;int n,t;
    cin>>kto;
    bool osoba=(kto=="Algosia");
    cin>>n>>t;

     N=(n-1)/32+1;
    R=n%32;
    MLAST=(1u<<R);
    inicjuj();
      for(int j=0;j<N;j++) MAKS.tab[j]=(0u-1);
    if(R!=0) MAKS.tab[N-1]=MAKS.tab[N-1]%MLAST;
    for(int j=0;j<t;j++)
    {
        mint zw;
    string dane;
    cin>>dane;int i=0;
   for(int j=0;j<N;j++){for(int z=0;z<((R==0 || j!=N-1)?32:R);z++){if(dane[i]>'0')zw.tab[j]|=(1u<<z);i++;}}
    Alicja[j].Init(zw,osoba);
    bool gotowa=0;
    do{
        cout<<Alicja[j].zagraj()<<"\n";cout.flush();
        char w;cin>>w;
         gotowa=Alicja[j].zwrotna(w);
    }while(!gotowa);
    mint odp=Alicja[j].wypisz();
    cout<<"! "<<odp.wypisz()<<"\n";cout.flush();
    }
}