#include<bits/stdc++.h>
#include "combo.h"
using namespace std;
using ll=long long;
const char dc[]={'A','B','X','Y'};
//int pi[100005];
//string S;
//int cnt=0;
//int press(string st){
// cnt++;
// int len=0,best=0;
// for(char c:st){
// while(len>0&&(len>=(int)S.size()||S[len]!=c))len=pi[len-1];
// if(len<(int)S.size()&&S[len]==c)len++;
// best=max(best,len);
// if(best==(int)S.size())break;
// }
// return best;
//}
string guess_sequence(int N){
string st="";
if(press("A")==1) st+='A';
else if(press("B")==1) st+='B';
else if(press("X")==1) st+='X';
else st+='Y';
for(int i=1;i<N;++i){
// cout<<i<<','<<st<<"!\n";
string tmp="";
char c1='#',c2='#',c3='#';
for(int j=0;j<4;++j)
if(st[0]!=dc[j]){
if(c1=='#')c1=dc[j];
else if(c2=='#') c2=dc[j];
else c3=dc[j];
}
// cout<<c1<<'_'<<c2<<'_'<<c3<<'\n';
tmp+=st+c1;
for(int j=0;j<4;++j)
if(st[0]!=dc[j])
tmp+=st+c2+dc[j];
int res = press(tmp);
// cout<<tmp <<'.'<<res<<'\n';
if(res==(int)st.size()+1) st+=c1;
else if(res==(int)st.size()+2)st+=c2;
else st+= c3;
}
// cout<<cnt<<"!\n";
return st;
}
//int main(){
// cin>>S;
// int n = (int)S.size();
// for(int i=1;i<n;++i){
// int j=pi[i-1];
// while(j>0&&S[i]!=S[j])j=pi[j-1];
// if(S[i]==S[j])++j;
// pi[i]=j;
// }
// cout<<guess_sequence(n);
//}
