#include "combo.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
char change(int x) { return "ABXY"[x]; }
int p[3];
int query(string &now, vector <int> a) {
string t = "";
for(int e : a) {
t = t + now;
t.pb(change(p[e / 3]));
t.pb(change(p[e % 3]));
}
return press(t);
}
std::string guess_sequence(int N) {
int t = press("AB");
int st = -1;
if(t >= 1) {
if(press("A")) st = 0;
else st = 1;
}
else {
if(press("X")) st = 2;
else st = 3;
}
string now; now.pb(change(st));
int pz = 0;
for(int i=0;i<4;i++) if(i != st) p[pz++] = i;
for(int i=2;i<=N;) {
if(i+1 <= N) {
int q1 = query(now, {1, 2, 5});
if(q1 == szz(now)) {
now.pb(change(p[2]));
i += 1;
}
else if(q1 == szz(now) + 2) {
int q2 = query(now, {1}) - szz(now);
if(q2 == 2) { now.pb(change(p[0])); now.pb(change(p[1])); }
else if(q2 == 1) { now.pb(change(p[0])); now.pb(change(p[2])); }
else { now.pb(change(p[1])); now.pb(change(p[2])); }
i += 2;
}
else {
int q2 = query(now, {3}) - szz(now);
if(q2 == 2) { now.pb(change(p[1])); now.pb(change(p[0])); }
else if(q2 == 1) { now.pb(change(p[1])); now.pb(change(p[1])); }
else { now.pb(change(p[0])); now.pb(change(p[0])); }
i += 2;
}
}
else {
string tnow = now;
tnow.pb(change(p[0]));
if(press(tnow) == N) now = tnow;
else {
tnow.pop_back();
tnow.pb(change(p[1]));
if(press(tnow) == N) now = tnow;
else {
tnow.pop_back();
tnow.pb(change(p[2]));
now = tnow;
}
}
i += 1;
}
}
return now;
}
