#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <ostream>
#include <random>
#include <string>
#include <string_view>
#include <time.h>
#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include <vector>
using namespace std;
template<size_t Nb>
struct out {
    bitset<Nb> bits;
    short lastone=Nb-1;
    size_t size;
    void init(size_t n, const bitset<Nb>& num) {bits=num;lastone=Nb-1;size=n/log2(3)+1;}
    void init(size_t n) {lastone=Nb-1;size=n/log2(3)+1;}
    bool pop2() {
        while (lastone>=0&&!bits[lastone])--lastone;
        if (lastone<0) return 0;
        if (lastone==0) return lastone=-1,bits[0]=0,1;
        bool res = bits.test(0);
        bits>>=1;
        --lastone;
        return res;
    }
    unsigned char pop3(bool requrent=0) {
        if (!requrent)--size;
        while (lastone>=0&&!bits[lastone])--lastone;
        if (lastone<0) return 0;
        if (lastone==0) return lastone=-1,bits[0]=0,1;
        bool carry=0;
        bitset<Nb> div3;
        div3[0]=bits[0];
        for (short i=1;i<lastone;++i) {
            if (bits[i]) {
                if (carry) carry=div3[i]=div3[i-1];
                else div3[i]=!div3[i-1];
            } else if (carry) div3[i]=!div3[i-1];
            else carry=div3[i]=div3[i-1];
        }
        if (div3[lastone-1]==carry) {
            for (short i=0;i<=lastone;++i)
                if (!bits[i].flip())break;
            return pop3(1)+1;
        }
        bits=div3;
        while (lastone>=0&&!bits[lastone])--lastone;
        return 0;
    }
};
template<size_t Nb>
struct in {
    bitset<Nb> bits;
    void reset() {bits.reset();}
    void push2(bool v) {
        bits<<=1;
        bits.set(0,v);
    }
    void push3(unsigned char v) {
        auto add = bits<<1;
    again:
        auto carry = add&bits;
        bits^=add;
        if (carry.any()){add=carry<<1;goto again;}
        for (int c=0;c<v;++c)
            for (short i=0;i<5000;++i)
                if (bits[i].flip())break;
    }
};
constexpr size_t maxN=5000;
struct game : in<maxN>,out<maxN> {
    using out<maxN>::size;
    using out<maxN>::init;
    using out<maxN>::pop2;
    using out<maxN>::pop3;
    using in<maxN>::push3;
    using in<maxN>::push2;
    size_t turns;
    void init(size_t n) {
        out<maxN>::init(n);
        in<maxN>::reset();
        turns=0;
    }
    static constexpr char conv[] {'K','N', 'P'};
    uint8_t move(uint8_t v) {
        ++turns;
        cout << conv[v] << endl;
        char op;cin>>op;
        if (op==conv[2])return 2;
        if (op==conv[1])return 1;
        if (op==conv[0])return 0;
        return 0;
    }
};

template<size_t Nb>
bitset<Nb> randommask(size_t seed, size_t len=Nb) {
    mt19937_64 rand(seed);
    bitset<Nb> res;
    for (size_t i=0;i<len;++i)
        res[i]=rand()&1;
    return res;
}
int sl=0;
constexpr int maskCount = 6561;
size_t play(game& engine, const vector<uint8_t>& send, vector<uint8_t>& recvie, size_t encode) {
    int8_t score=0;
    vector<uint8_t> moves;
    for (int c=0;c<8;) {
        uint8_t opponent;
        switch (score) {
        case 1:
            opponent = engine.move(1);
            assert(opponent==0);
            score=0;
            break;
        case -1:
            opponent = engine.move(0);
            assert(opponent==1);
            score=0;
            break;
        case 0:
            const auto mymove = encode%3;encode/=3;
            opponent = engine.move(mymove);
            moves.push_back(opponent);
            score=opponent==mymove?0:(3+opponent-mymove)%3==1?1:-1;
            ++c;
            break;
        }
    }
    size_t decode=0;
    while (!moves.empty())decode+=decode<<1,decode+=moves.back(),moves.pop_back();

    int repeat=0;
    size_t id=0;
    while (id<send.size()) {
        uint8_t opponent;
        switch (score) {
        case 1:
            opponent = engine.move(1);
            assert(opponent==0);
            score=0;
            break;
        case -1:
            opponent = engine.move(0);
            assert(opponent==1);
            score=0;
            break;
        case 0:
            const auto mymove = send[id++];
            opponent = engine.move(mymove);
            recvie.push_back(opponent);
            score=opponent==mymove?0:(3+opponent-mymove)%3==1?1:-1;
            if (opponent==mymove) ++repeat;
            break;
        }
    }
    //if (sl) cerr << engine.turns << ' ' << '(' << repeat << ')' << '\n';
    return decode;
}
void random3mask(size_t seed, uint8_t* mask, size_t len) {
    mt19937_64 rand(seed);
    for (size_t i=0;i<len;++i)
        mask[i]=rand()%3;
}
size_t count3mask(const uint8_t* base, const uint8_t* add, size_t n) {
    size_t res=0;
    for (size_t i=0;i<n;++i)
        if (base[i]+add[i]==0||base[i]+add[i]==3)
            ++res;
    return res;
}
void add3mask(vector<uint8_t>& base, const uint8_t* add, size_t n) {
    for (size_t i=0;i<n;++i)
        base[i]=(base[i]+add[i])%3;
}
void rem3mask(vector<uint8_t>& base, const uint8_t* add, size_t n) {
    for (size_t i=0;i<n;++i)
        base[i]=(3+base[i]-add[i])%3;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    uint8_t* _A[maskCount],*_B[maskCount],*C;
    uint8_t** A=_A,**B=_B;
    string s;int n,t;
    cin>>s>>n>>t;
    int m = n/log2(3)+1;
    for (int i=0;i<maskCount;++i) {
        random3mask(69+i,A[i]=(uint8_t*)calloc(m, 1),m),random3mask(2137+i,B[i]=(uint8_t*)calloc(m, 1),m);
        /*for (int j=0;j<m;++j) cerr << +A[i][j] << ' ';
        cerr << '\n';
        for (int j=0;j<m;++j) cerr << +B[i][j] << ' ';
        cerr << '\n';*/
    }
    if (s.front()=='B')swap(A,B),sl=1;
    game g;
    while (t--) {
        cin >> s;
        g.init(n);
        for (int i=0;i<n;++i)
            g.out::bits[i]=s[i]-'0';
        vector<uint8_t> mask,out;
        while (g.size)
            mask.push_back(g.pop3());
        size_t maxid=0, maxv=0;
        for (size_t i=0;i<maskCount;++i) {
            auto v=count3mask(mask.data(), A[i], m);
            if (v>maxv)maxid=i,maxv=v;
        }
        add3mask(mask, A[maxid], m);
        //for (auto&& ch : mask) cerr << +ch << ' ';
        auto op = play(g, mask, out, maxid);
        //for (auto&& ch : out) cerr << +ch << ' ';
        rem3mask(out, B[op], m);
        for (int i=m-1;i>=0;--i)
            g.push3(out[i]);
        for (int i=0;i<n;++i)
            s[i]='0'+g.in::bits[i];
        cout << '!' << s << endl;
    }
}