#include<bits/stdc++.h>
using namespace std;
mt19937 rng(4478264);
int RAND(int a, int b)
{
    return uniform_int_distribution<int>(a,b)(rng);
}
const int b1=9,b2=11;
vector<vector<int>>Ziomy;
map<vector<int>,vector<int>>Ziomy2;
vector<int>TT;
bool cmp(vector<int>A, vector<int>B)
{
    int ilosc=0;
    for(int u : A)
    {
        if(u==0){ilosc++;}
    }
    for(int u : B)
    {
        if(u==0){ilosc--;}
    }
    return ilosc<0;
}
void F(int v)
{
    if(v==b2)
    {
        Ziomy.push_back(TT);
        return;
    }
    TT.push_back(0);
    F(v+1);
    TT.pop_back();
    TT.push_back(1);
    F(v+1);
    TT.pop_back();
}
int mod2(const vector<int>&U)
{
    return U[0];
}
int mod3(const vector<int>&U)
{
    int w=0;
    int poww=1;
    for(int u : U)
    {
        if(u==1){w=(w+poww)%3;}
        poww=(poww*2)%3;
    }
    return w;
}
void divide2(vector<int>&U)
{
    for(int i=1;i<(int)U.size();i++)
    {
        U[i-1]=U[i];
    }
    U[(int)U.size()-1]=0;
}
void divide3(vector<int>&U)
{
    int obecna=0;
    for(int i=(int)U.size()-1;i>=0;i--)
    {
        obecna=obecna*2+U[i];
        U[i]=obecna/3;
        obecna%=3;
    }
}
vector<int>Sum(vector<int>A, vector<int>B)
{
    vector<int>W(A.size());
    int reszta=0;
    for(int i=0;i<(int)A.size();i++)
    {
        reszta+=A[i]+B[i];
        W[i]=reszta%2;
        reszta/=2;
    }
    return W;
}
void multiple2(vector<int>&U)
{
    for(int i=(int)U.size()-2;i>=0;i--)
    {
        U[i+1]=U[i];
    }
    U[0]=0;
}
void multiple3(vector<int>&U)
{
    vector<int>U2=U;
    multiple2(U2);
    U=Sum(U,U2);
}
int GetLiczba(const vector<int>&U)
{
    int w=0;
    int poww=1;
    for(int u : U)
    {
        if(u==1){w+=poww;}
        poww*=2;
    }
    return w;
}
int N(char z)
{
    if(z=='N'){return 0;}
    if(z=='P'){return 1;}
    if(z=='K'){return 2;}
}
int Mecz(int a, int b)
{
    if(a==b){return 0;}
    if((a+1)%3==b){return 1;}
    return -1;
}
const char Tlumacz[3]={'N','P','K'};
int bilans=0;
int WczytajNumer(int x)
{
    cout<<Tlumacz[x]<<endl;
    char z2;
    cin>>z2;
    int w=N(z2);
    bilans+=Mecz(x,w);
    return w;
}
vector<int>Trojkowy(vector<int>liczba, int ile)
{
    vector<int>W;
    for(int i=0;i<ile;i++)
    {
        W.push_back(mod3(liczba));
        divide3(liczba);
    }
    return W;
}
int XOR[2][5009];
vector<int>liczba,liczba3;
int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed<<setprecision(10);
    F(0);
    sort(Ziomy.begin(),Ziomy.end(),cmp);
    for(int i=0;i<(1<<b1);i++)
    {
        vector<int>U;
        int u=i;
        for(int j=0;j<b1;j++)
        {
            U.push_back(u%2);
            u>>=1;
        }
        Ziomy2[Ziomy[i]]=U;
    }
    int N$,n,t,t2;
    string KimJestem;
    cin>>KimJestem;
    cin>>n>>N$;
    if(KimJestem=="Algosia"){t=0;}
    else if(KimJestem=="Bajtek"){t=1;}
    t2=t^1;
    //ofstream //out(to_string(t)+".txt");
    //out<<"n="<<n<<" N$="<<N$<<endl;
for(int I$=1;I$<=N$;I$++)
{
    liczba.clear();
    liczba3.clear();
    bilans=0;
    for(int i=0;i<n;i++)
    {
        XOR[0][i]=RAND(0,1);
        XOR[1][i]=RAND(0,1);
        char u;cin>>u;
        liczba.push_back((u-'0')^XOR[t][i]);
    }
    //out<<"bilans="<<bilans<<endl;
    int leng=ceil(log(2)/log(3)*n+0.5);
    double CEL=max((double)10,log(2)*n+1.5);
    double L[2]={0,0};
    liczba3=Trojkowy(liczba,leng);
    vector<int>Znaki;
    while((int)liczba.size()%b1!=0){liczba.push_back(0);}
    vector<int>W2,W3;
    vector<int>Bufor;
    int bufor2=0;
    int h=0;
    while(h<(int)liczba.size())
    {
        int poww=1,w=0;
        for(int j=0;j<b1;j++)
        {
            if(liczba[h]==1)
            {
                w+=poww;
            }
            poww*=2;
            h++;
        }
        for(int j=0;j<b2;j++)
        {
            Znaki.push_back(Ziomy[w][j]);
        }
    }
    reverse(liczba3.begin(),liczba3.end());
    while(Znaki.size()<5000){Znaki.push_back(0);}
    while(liczba3.size()<5000){liczba3.push_back(0);}
    reverse(Znaki.begin(),Znaki.end());
    reverse(liczba3.begin(),liczba3.end());
    while(true)
    {
        //out<<"bilans="<<bilans<<endl;
        if(L[0]>CEL && L[1]>CEL){break;}
        if(bilans==0)
        {
            int u=WczytajNumer(liczba3.back());
            liczba3.pop_back();
            W3.push_back(u);
            L[t]+=log(3);
            L[t2]+=log(3);
        }
        else
        {
            if(L[t]<L[t2]||(L[t]==L[t2]&&t==0))
            {//ja przesylam info
                bufor2++;
                if(bilans==1)
                {//musze przegrac
                    WczytajNumer(Znaki.back());
                    Znaki.pop_back();
                }
                else if(bilans==-1)
                {//musze wygrac
                    WczytajNumer(Znaki.back()^1);
                    Znaki.pop_back();
                }
            }
            else
            {//ziomus wysyla info
                int u;
                if(bilans==1)
                {//musze przegrac
                    u=WczytajNumer(1);
                    Bufor.push_back(u^1);
                }
                else if(bilans==-1)
                {//musze wygrac
                    u=WczytajNumer(0);
                    Bufor.push_back(u);
                }
            }
        }
        if((int)Bufor.size()==b2)
        {
            vector<int>Temp=Ziomy2[Bufor];
            for(int u : Temp){W2.push_back(u);}
            L[t]+=log(2)*b1;
            Bufor.clear();
        }
        if(bufor2==b2)
        {
            L[t2]+=log(2)*b1;
            bufor2=0;
        }
    }
    vector<int>W(n);
    while(W3.size()>leng){W3.pop_back();}
    while(W3.size()<leng){W3.push_back(0);}
    reverse(W3.begin(),W3.end());
    vector<int>POWW(n);POWW[0]=1;
    for(int i=0;i<leng;i++)
    {
        for(int j=0;j<W3[i];j++)
        {
            W=Sum(W,POWW);
        }
        multiple3(POWW);
    }
    for(int i=0;i<min(n,(int)W2.size());i++)
    {
        W[i]=W2[i];
    }
    //out<<"t="<<t<<" "<<"xd"<<endl;
    cout<<"! ";
    for(int i=0;i<n;i++)
    {
        W[i]^=XOR[t2][i];
        cout<<W[i];
        //out<<W[i];
    }
    //out<<endl;
    cout<<endl;
}
    return 0;
}