#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include "combo.h"
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#ifdef LOCAL
#include </home/linux/debug.h>
#define dbg(...) cout << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", _print(__VA_ARGS__)
#else
#define dbg(...)
#endif
string guess_sequence(int N)
{
string ans;
vector<string> a[N+1];
if(press("A") == 1)
ans = "A";
else if(press("B")==1)
ans = "B";
else if(press("X") == 1)
ans = "X";
else
ans = "Y";
a[0] = {"A","B","X","Y"};
for(int i = 1;i<N;i++)
{
for(string x:a[0])
if(x!=ans)
a[i].pb(x);
}
for(int i = 1;i<N-1;i++)
{
if(sz(a[i]) == 1)
{
ans+=a[i][0];
continue;
}
bool did = 0;
for(int j = 0;j<sz(a[i])-1&&!did;j++)
{
for(int k = 0;k<sz(a[i+1])&&!did;k++)
{
int x = press(ans+a[i][j]+a[i+1][k]);
if(x == i+2)
{
ans+=a[i][j]+a[i+1][k];
did = 1;
i++;
}
else if(x == i+1)
{
ans+=a[i][j];
a[i+1].erase(a[i+1].begin()+k);
did = 1;
}
else
break;
}
}
if(!did)
ans+=a[i].back();
}
if(sz(ans) == N)
return ans;
if(sz(a[N-1]) == 1)
ans+=a[N-1][0];
else
{
for(int i = 0;i<sz(a[N-1])-1;i++)
if(press(ans+a[N-1][i])==N)
{
ans+=a[N-1][i];
break;
}
if(sz(ans)<N)
ans+=a[N-1].back();
}
return ans;
}
