#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> rnd(0,1000000000);
int randint(int a,int b){
return a+rnd(mt)%(b-a+1);
}
std::string guess_sequence(int N) {
string t="ABXY";
vector<vector<char>> st(N,{'A','B','X','Y'});
int idx=1;
string ans="";
{
int x=press("AB");
if(x){
if(press("A"))ans="A";
else ans="B";
}else{
if(press("X"))ans="X";
else ans="Y";
}
}
rng(j,1,N){
st[j].erase(find(all(st[j]),ans[0]));
}
int cnt=0;
while(idx<N){
string s=ans;
while(s.size()<N){
vector<int> vs;
rep(i,4){
if(find(all(st[s.size()]),t[i])!=st[s.size()].end()){
vs.push_back(i);
}
}
s+=t[vs[randint(0,vs.size()-1)]];
}
// cout<<"s : "<<s<<endl;
int ret=press(s);
cnt++;
// cout<<"ret : "<<ret<<endl;
rng(i,idx,ret){
ans+=s[i];
st[i]={s[i]};
}
if(ret!=N){
st[ret].erase(find(all(st[ret]),s[ret]));
}
idx=ret;
}
assert(cnt<=N+10);
return ans;
}
