#include "combo.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using ll=long long;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
void _print(vector<pii> x) {cerr<<"["; for(auto e:x) cerr<<"{"<<e.first<<","<<e.second<<"} ,"; cerr<<"]";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"]";
dbg(T...);
}
#define debug(...) cerr<<"[\""<<#__VA_ARGS__<<"\"]: [",dbg(__VA_ARGS__);
char a[4]={'A','B','X','Y'};
vector<char> ar;
std::string guess_sequence(int N) {
// debug(N);
string ans;
for(int i=0;i<3;i++) {
string temp; temp.push_back(a[i]);
int res=press(temp);
if(res==1) {
ans+=a[i]; break;
}
}
if(ans.empty()) ans.push_back(a[3]);
for(int i=0;i<4;i++) {
if(a[i]!=ans[0]) ar.push_back(a[i]);
}
bool past=false;
vector<char> past_list;
vector<string> guess_list;
for(auto e:ar) {
for(auto f:ar) {
string temp; temp.push_back(e); temp.push_back(f);
guess_list.push_back(temp);
}
}
// debug(guess_list);
for(int i=2;i<=N;i++) {
int len=ans.size();
if(past) {
if(i==N) {
string temp=ans; temp.push_back(past_list[0]);
if(press(temp)==N) return temp;
ans.push_back(past_list[1]);
return ans;
}
else {
string temp;
for(int j=0;j<2;j++) {
temp+=ans; temp.push_back(past_list[0]);
temp.push_back(ar[j]);
}
int res=press(temp);
if(res==len) {
ans.push_back(past_list[1]);
past=false;
}
else if(res==len+1) {
ans.push_back(past_list[0]);
ans.push_back(ar[2]); i++;
past=false;
}
else {
ans.push_back(past_list[0]);
}
}
}
else {
if(i==N) {
for(int j=0;j<2;j++) {
string temp=ans+ar[j];
if(press(temp)==N) return temp;
}
ans.push_back(ar[2]); return ans;
}
string temp;
for(int j=0;j<4;j++) {
temp+=ans+guess_list[j];
}
int res=press(temp);
if(res==len) {
ans.push_back(ar[2]);
}
else if(res==len+1) {
ans.push_back(ar[1]);
}
else {
temp="";
for(int j=0;j<2;j++) {
temp+=ans+guess_list[j];
}
int res2=press(temp);
if(res2==len) {
ans+=guess_list[3]; i++;
}
else if(res2==len+1) {
ans+=guess_list[2]; i++;
}
else {
ans.push_back(ar[0]);
past_list.clear();
past_list.push_back(ar[0]);
past_list.push_back(ar[1]);
past=true;
}
}
}
}
return ans;
}
