#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n)    fwd(i, 0, n)
#define all(X)       X.begin(), X.end()
#define sz(X)        int(size(X))
#define pb           push_back
#define eb           emplace_back
#define st           first
#define nd           second
using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using ld = long double;
#ifdef LOC
auto SS = signal(6, [](int) {
	*(int *)0 = 0;
});
#	define DTP(x, y)                                      \
		auto operator<<(auto &o, auto a)->decltype(y, o) { \
			o << "(";                                      \
			x;                                             \
			return o << ")";                               \
		}
DTP(o << a.st << ", " << a.nd, a.nd);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) {
	((cerr << x << ", "), ...) << '\n';
}
#	define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#	define deb(...) 0
#endif

struct UnsignedBigInt {
	// mnożymy przez małe chłopki, także można podbić base
	static const long long BASE = 10000000000000LL; // 10^13
	vector<long long> digits;

	UnsignedBigInt(long long x = 0) {
		digits.clear();
		while (x > 0) {
			digits.push_back(x % BASE);
			x /= BASE;
		}
	}
	static int compare(const UnsignedBigInt &a, const UnsignedBigInt &b) {
		if (a.digits.size() != b.digits.size())
			return (a.digits.size() < b.digits.size() ? -1 : 1);
		for (int i = (int)a.digits.size() - 1; i >= 0; i--) {
			if (a.digits[i] != b.digits[i])
				return (a.digits[i] < b.digits[i] ? -1 : 1);
		}
		return 0;
	}
	bool less_than(const UnsignedBigInt &other) const {
		return compare(*this, other) < 0;
	}
	bool greater_than(const UnsignedBigInt &other) const {
		return compare(*this, other) > 0;
	}
	bool less_equal_to(const UnsignedBigInt &other) const {
		return compare(*this, other) <= 0;
	}
	bool greater_equal_to(const UnsignedBigInt &other) const {
		return compare(*this, other) >= 0;
	}
	bool equal_to(const UnsignedBigInt &other) const {
		return compare(*this, other) == 0;
	}
	bool not_equal_to(const UnsignedBigInt &other) const {
		return compare(*this, other) != 0;
	}
	bool equal_to(long long x) const {
		return this->equal_to(UnsignedBigInt(x));
	}
	void remove_leading_zeros() {
		while (!digits.empty() && digits.back() == 0)
			digits.pop_back();
	}
	void add(const UnsignedBigInt &other) {
		int max_digits = (int)max(digits.size(), other.digits.size());
		digits.resize(max_digits);
		long long carry = 0;
		for (int i = 0; i < max_digits; i++) {
			long long cur = carry;
			if (i < (int)digits.size())
				cur += digits[i];
			if (i < (int)other.digits.size())
				cur += other.digits[i];
			digits[i] = cur % BASE;
			carry = cur / BASE;
		}
		if (carry > 0)
			digits.push_back(carry);
	}
	void subtractSmaller(const UnsignedBigInt &other) {
		long long carry = 0;
		for (size_t i = 0; i < digits.size(); i++) {
			long long cur = digits[i] - carry;
			if (i < other.digits.size())
				cur -= other.digits[i];
			if (cur < 0) {
				cur += BASE;
				carry = 1;
			} else {
				carry = 0;
			}
			digits[i] = cur;
		}
		remove_leading_zeros();
	}
	UnsignedBigInt addPositiveInt(long long x) {
		long long carry = x;
		int i = 0;
		while (carry > 0) {
			if (i == (int)digits.size())
				digits.push_back(0);
			long long cur = digits[i] + carry;
			digits[i] = cur % BASE;
			carry = cur / BASE;
			i++;
		}
		return *this;
	}
	void mulPositiveInt(long long x) {
		long long carry = 0;
		for (int i = 0; i < (int)digits.size(); i++) {
			long long cur = digits[i] * x + carry;
			digits[i] = cur % BASE;
			carry = cur / BASE;
		}
		while (carry > 0) {
			digits.push_back(carry % BASE);
			carry /= BASE;
		}
	}
	long long divPositiveInt(long long x) {
		long long remainder = 0;
		for (int i = (int)digits.size() - 1; i >= 0; i--) {
			long long cur = digits[i] + remainder * BASE;
			digits[i] = cur / x;
			remainder = cur % x;
		}
		remove_leading_zeros();
		return remainder;
	}
};

UnsignedBigInt range_size(
	const UnsignedBigInt &range_start, const UnsignedBigInt &range_end) {
	UnsignedBigInt range_size = range_end;
	range_size.subtractSmaller(range_start);
	return range_size;
}

pair<UnsignedBigInt, UnsignedBigInt> splitIntoThree(
	const UnsignedBigInt &start, const UnsignedBigInt &end) {
	UnsignedBigInt tot_range_size = range_size(start, end);
	UnsignedBigInt subrange_size = tot_range_size;
	subrange_size.divPositiveInt(3);
	UnsignedBigInt first_split = start;
	first_split.add(subrange_size);
	UnsignedBigInt second_split = first_split;
	second_split.add(subrange_size);
	UnsignedBigInt third_range_size = range_size(second_split, end);

	if (range_size(subrange_size, third_range_size).greater_than(1)) {
		second_split.addPositiveInt(1);
	}
	return {first_split, second_split};
}

const long long gora_ulamka = 5000 - 3801;
const long long dol_ulamka = 5000;

UnsignedBigInt biasedSplit(
	const UnsignedBigInt &start,
	const UnsignedBigInt &end,
	const int small_side) {
	UnsignedBigInt tot_range_size = range_size(start, end);
	UnsignedBigInt small_side_size = tot_range_size;
	small_side_size.mulPositiveInt(gora_ulamka);
	small_side_size.divPositiveInt(dol_ulamka);
	if (small_side_size.equal_to(0) && tot_range_size.greater_than(1)) {
		small_side_size.addPositiveInt(1);
	}
	UnsignedBigInt split_point = start;
	if (small_side == 0) {
		split_point.add(small_side_size);
	} else {
		split_point.add(tot_range_size);
		split_point.subtractSmaller(small_side_size);
	}
	return split_point;
}

UnsignedBigInt bigIntFromBinaryString(const string &s) {
	UnsignedBigInt res;
	for (char c : s) {
		res.mulPositiveInt(2);
		if (c == '1')
			res.addPositiveInt(1);
	}
	return res;
}

string binaryStringFromBigInt(const UnsignedBigInt &x, const int N) {
	string res;
	UnsignedBigInt cur = x;
	while (!cur.equal_to(0)) {
		long long rem = cur.divPositiveInt(2);
		res += (rem == 1 ? '1' : '0');
	}
	while ((int)res.size() < N) {
		res += '0';
	}
	reverse(res.begin(), res.end());
	return res;
}

string get_random_binary_string(int n, mt19937_64 &rng) {
	string res;
	rep(i, n) {
		int val = rng() % 2;
		res += (val ? '1' : '0');
	}
	return res;
}

string xor_with_binary_string(const string &s, const string &xor_mask) {
	string res = s;
	for (size_t i = 0; i < s.size(); ++i)
		if (xor_mask[i] == '1')
			res[i] = (s[i] == '0' ? '1' : '0');
	return res;
}

void solve_testcase(int my_id, int N, mt19937_64 &rng) {
	int other_id = my_id ^ 1;
	string my_data;
	cin >> my_data;
	string random_xor = get_random_binary_string(N, rng);
	my_data = xor_with_binary_string(my_data, random_xor);

	UnsignedBigInt my_data_bigint = bigIntFromBinaryString(my_data);

	UnsignedBigInt my_range_start, my_range_end;
	UnsignedBigInt other_range_start, other_range_end;
	my_range_start = other_range_start = UnsignedBigInt(0);
	my_range_end = other_range_end =
		bigIntFromBinaryString("1" + string(N, '0'));

	// i wygrywa z (i + 1) % 3
	array<char, 3> symbols = {'P', 'K', 'N'};
	map<char, char> loses_to;
	map<char, char> beats;
	rep(i, 3) {
		loses_to[symbols[i]] = symbols[(i + 1) % 3];
		beats[symbols[i]] = symbols[(i - 1 + 3) % 3];
	}

	int my_advantage = 0;

	while (true) {
		UnsignedBigInt my_range_size = range_size(my_range_start, my_range_end);
		UnsignedBigInt other_range_size =
			range_size(other_range_start, other_range_end);
		if (my_range_size.equal_to(1) && other_range_size.equal_to(1)) {
			break;
		}
		if (my_advantage ==
			0) { // draw -> optimal log2(3) information transmition
			array<int, 2> symbol_shift_of_id;
			rep(id, 2) symbol_shift_of_id[id] = int(rng() % 3);
			map<int, char> my_interval_to_symbol;
			map<char, int> other_symbol_to_interval;
			rep(i, 3) {
				char my_sym = symbols[(i + symbol_shift_of_id[my_id]) % 3];
				char other_sym =
					symbols[(i + symbol_shift_of_id[other_id]) % 3];
				my_interval_to_symbol[i] = my_sym;
				other_symbol_to_interval[other_sym] = i;
			}
			// check in which interval my data is and send its symbol
			auto [first_range_split, second_range_split] =
				splitIntoThree(my_range_start, my_range_end);
			char my_symbol = '#';
			if (my_data_bigint.greater_equal_to(second_range_split)) {
				my_symbol = my_interval_to_symbol[2];
				my_range_start = second_range_split;
			} else if (my_data_bigint.greater_equal_to(first_range_split)) {
				my_symbol = my_interval_to_symbol[1];
				my_range_start = first_range_split;
				my_range_end = second_range_split;
			} else {
				my_symbol = my_interval_to_symbol[0];
				my_range_end = first_range_split;
			}
			cout << my_symbol << endl;
			char other_symbol;
			cin >> other_symbol;
			int other_interval = other_symbol_to_interval[other_symbol];
			auto [other_first_split, other_second_split] =
				splitIntoThree(other_range_start, other_range_end);
			if (other_interval == 0) {
				other_range_end = other_first_split;
			} else if (other_interval == 1) {
				other_range_start = other_first_split;
				other_range_end = other_second_split;
			} else {
				other_range_start = other_second_split;
			}
			// update advantage
			if (loses_to[my_symbol] == other_symbol) {
				my_advantage = 1;
			} else if (beats[my_symbol] == other_symbol) {
				my_advantage = -1;
			}
		} else { // someone winning, must end advantage
			int id_with_larger_range = rng() % 2;
			if (my_range_size.greater_than(other_range_size)) {
				id_with_larger_range = my_id;
			} else if (other_range_size.greater_than(my_range_size)) {
				id_with_larger_range = other_id;
			}
			int small_side = rng() % 2;
			int large_side = small_side ^ 1;
			char draw_symbol = 'P';
			char advantage_end_symbol =
				((my_id ^ id_with_larger_range) ^ (my_advantage != 1 ? 1 : 0))
					? 'N'
					: 'K';
			// other is disadvantaged, we must give him information
			// draw = small interval, advantage_end = large interval
			// trade return to greater information throughput for smaller gain
			if (id_with_larger_range == my_id) {
				map<int, char> my_interval_to_symbol;
				my_interval_to_symbol[small_side] = draw_symbol;
				my_interval_to_symbol[large_side] = advantage_end_symbol;
				UnsignedBigInt split_point =
					biasedSplit(my_range_start, my_range_end, small_side);
				char my_symbol = '#';
				if (my_data_bigint.greater_equal_to(split_point)) {
					my_symbol = my_interval_to_symbol[1];
					my_range_start = split_point;
				} else {
					my_symbol = my_interval_to_symbol[0];
					my_range_end = split_point;
				}
				cout << my_symbol << endl;
				char other_symbol;
				// other symbol is draw_symbol always
				cin >> other_symbol;
				if (my_symbol == advantage_end_symbol) {
					my_advantage = 0;
				}
			} else {
				map<char, int> other_symbol_to_interval;
				other_symbol_to_interval[draw_symbol] = small_side;
				other_symbol_to_interval[advantage_end_symbol] = large_side;
				char my_symbol = draw_symbol; // always draw symbol
				cout << my_symbol << endl;
				char other_symbol;
				cin >> other_symbol;
				int other_interval = other_symbol_to_interval[other_symbol];
				UnsignedBigInt split_point =
					biasedSplit(other_range_start, other_range_end, small_side);
				if (other_interval == 0) {
					other_range_end = split_point;
				} else {
					other_range_start = split_point;
				}
				if (other_symbol == advantage_end_symbol) {
					my_advantage = 0;
				}
			}
		}
	}

	// decoded data
	string result = binaryStringFromBigInt(other_range_start, N);
	result = xor_with_binary_string(result, random_xor);
	cout << "! " << result << endl;
}

int32_t main() {
	string id_string;
	cin >> id_string;
	int my_id = id_string[0] == 'A' ? 0 : 1; // Anastazja = 0, Bogumił = 1
	int N, T;
	cin >> N >> T;
	mt19937_64 rng(
		2128 * 70); // 2128 = Ile Kj w 100 gram kranczips keczup stiks
					//   70 = ile gram w opakowaniu kranczips keczup stiks
	rep(i, T) {
		solve_testcase(my_id, N, rng);
	}
#ifdef LOCF
	cout.flush();
	cerr << "- - - - - - - - -\n";
	(void)!system(
		"grep VmPeak /proc/$PPID/status | sed s/....kB/\' MB\'/1 >&2"); // 4x.kB
																		// ....kB
#endif
	return 0;
}