#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a,  b) for (auto i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ITH_BIT(m, i) ((m)>>(i) & 1)
#define PPC(x) __builtin_popcount(x)

#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = std::min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = std::max(a, (T1)b);	}

const int maxN = 5028, N3 = 3158;

template <int B>
struct BigNum
{
	std::vector <int> T;

	void normalise()
	{
		while (T.size() != 1 and T.back() == 0)
			T.pop_back();
	}

	int operator[] (int i)	const
	{	return T[i];	}	

	void operator+= (BigNum& other)
	{
		T.resize(std::max(T.size(), other.T.size()));
		int carry = 0;
		FOR(i, 0, SZ(T))
		{
			int b = T[i] + carry + (i < SZ(other.T) ? other[i] : 0);
			T[i] = b % B;
			carry = b >= B;
		}
		if (carry == 1)
			T.push_back(1);
	}

	long long operator/= (int m)	//|m|<B
	{
		long long mod = 0;
		for (int i=T.size()-1; i>=0; i--)
		{
			mod = mod * B + T[i];
			T[i] = mod / m;
			mod %= m;
		}
		normalise();
		return mod;
	}

	BigNum operator+ (BigNum& other)
	{
		BigNum res(*this);
		res += other;
		return res;
	}

	bool isZero()
	{
		return T.empty() or T.back() == 0;
	}

	void fromStr(const char* s = "0")
	{
		int m = strlen(s);
		T.resize(m);
		FOR(i, 0, m)
			T[i] = s[i] - '0';
		std::ranges::reverse(T);		
		normalise();
	}
};

BigNum<3> two2three(BigNum<2>& x)
{
	std::vector <int> temp[3];
	int ind = 0;
	x.normalise();

	for (int dig : x.T)
	{
		temp[ind].push_back(dig);
		ind ^= 1;
	}

	BigNum<4> A { temp[0] };
	BigNum<4> B { temp[1] };
	A.normalise(), B.normalise();

	A += B;
	A += B;

	while (not A.isZero())
		temp[2].push_back(A /= 3);

	return BigNum<3> { temp[2] };
}

BigNum<2> three2two(BigNum<3>& x)
{
	x.normalise();
	std::vector <int> digs;
	while (not x.isZero())
		digs.push_back(x /= 2);
	return BigNum<2> { digs };
}

char id[28], input[maxN];
int n;

std::vector <int> myOrd, hisOrd, myDigs, hisDigs;
int myIt, hisIt;

int play(int x)
{
	static const std::string str = "PKN";
	static const std::map <char, int> M = {{'P', 0}, {'K', 1}, {'N', 2}};

	printf("%c\n", str[x]);
	fflush(stdout);

	char buf[7];
	scanf ("%s", buf);
	return M.at(buf[0]);
}

void ans(BigNum<2>& x)
{
	int xDigs = SZ(x.T);
	int lZeros = n - xDigs;
	printf("! ");
	while (lZeros--)
		printf("0");
	FORD(i, xDigs - 1, -1)
		printf("%d", x.T[i]);
	printf("\n");
	fflush(stdout);
}

void ans()
{
	BigNum<3> as3 { hisDigs };
	as3.normalise();
	BigNum<2> as2 = three2two(as3);
	as2.normalise();
	ans(as2);
}

int digMy()
{
	return myDigs[myOrd[myIt++]];
}

void digHis(int d)
{
	hisDigs[hisOrd[hisIt++]] = d;
}

void enrand(int& d, int x)
{
	d += (id[0] == 'A' ?  x : 3 - x);
	d %= 3; 
}

void derand(int& d, int x)
{
	d += (id[0] == 'A' ? x : 3 - x);
	d %= 3;
}

void shuffleOrder(int seed)
{
	myIt = hisIt = 0;
	auto rng = std::default_random_engine {seed};

	if (id[0] == 'A')
	{
		std::ranges::shuffle(myOrd, rng);
		std::ranges::shuffle(hisOrd, rng);
	}
	else
	{
		std::ranges::shuffle(hisOrd, rng);
		std::ranges::shuffle(myOrd, rng);
	}
}

void setupOrder()
{
	myOrd.resize(N3);
	hisOrd.resize(N3);

	std::iota(myOrd.begin(), myOrd.end(), 0);
	std::iota(hisOrd.begin(), hisOrd.end(), 0);
}

int setupSeed()
{
	srand(clock() ^ id[0]);

	int myPart = rand() % 3;

	int hisPart = play(myPart);

	if (myPart != hisPart)
		play(hisPart);

	int ret = N3 * (myPart + 17) + maxN * (hisPart + 2) * (hisPart + 3);
	return ret;
}

void load()
{
	scanf ("%s", input);
	BigNum<2> myBin;
	myBin.fromStr(input);
	BigNum<3> tern = two2three(myBin);
	tern.normalise();

	myDigs = tern.T;
	myDigs.resize(N3, 0);
	hisDigs.resize(N3, 0);
}

void solve()
{
	load();

	int seed = setupSeed();
	shuffleOrder(seed);

	FOR(_, 0, N3)
	{
		int x = rand() % 3;
		int my = digMy(), myOrig = my;
		enrand(my, x);
		int his = play(my);
		derand(his, x);
		int hisOrig = his;
		digHis(his);

		if (myOrig != hisOrig)
			play(hisOrig);
	}
	ans();
}

int main()
{
	int tc = 1;
	scanf ("%s%d%d", id, &n, &tc);
	setupOrder();

	FOR(cid, 1, tc+1)
	{
//		printf("Case #%d: ", cid);
		solve();
	}
	return 0;
}