#include "combo.h"
#include<bits/stdc++.h>
using namespace std;
std::string guess_sequence(int N){
set<char> s;
s.insert('A');
s.insert('B');
s.insert('X');
s.insert('Y');
string res;
vector<string> pr;
for(int i=1;i<=N;i++){ //cout<<"i:"<<i<<"\n";
//each i for ith character
//in first i we have 4 choices
//afterthat we have 3 choices always
char c;
if(i==1){
for(auto x:s){
string aux=res;
aux+=x;
int ans=press(aux);
// cout<<aux<<"\n";
// int ans;
// cin>>ans;
if(ans==i){
//ok this is part of the string
res=aux;
c=x;
break;
}
}
if(i==1)s.erase(c);
for(auto x:s){
for(auto y:s){
string p;
p+=x;
p+=y;
pr.push_back(p);
}
}
// cout<<"pr.size():"<<pr.size()<<"\n";
// for(int i=0;i<pr.size();i++){
// cout<<pr[i]<<" ";
// } cout<<"\n";
}else{
if(i==N){
for(auto x:s){
string aux=res;
aux+=x;
int ans=press(aux);
// cout<<aux<<"\n";
// int ans;
// cin>>ans;
if(ans==i){
//ok this is part of the string
res=aux;
break;
}
}
}else{
//query 2 at once
for(int k=0;k<9;k+=3){
string aux=res;
string pre=res;
aux+=pr[k];
aux+=pre;
aux+=pr[k+1];
aux+=pre;
aux+=pr[k+2];
int ans=press(aux);
// cout<<aux<<"\n";
// int ans;
// cin>>ans;
int ch=0;
if(ans==i+1){
for(int j=k;j<k+3;j++){
string aux2=res;
aux2+=pr[j];
int ans=press(aux2);
// cout<<aux2<<"\n";
// cin>>ans;
if(ans==i+1){
res=aux2;
break;
}
}
ch=1;
}
if(ch==1)break;
}
i+=1;
}
}
}
return res;
//how can we bring down the number of presses more?
//we get length of largest substring that is prefix of S
//finding next 2 positions take 6 queries
//can we bring it down?
//we can do like *xy*yc in 1 query
//*xc*cy in next
//*yx*cx in next
//*yy*xx*cc in next
//then singularly everyother
//this will in worst case take 7 queries if it is cc
//what if all 3 3
//xy*yc*cy
//xc*yx*cx
//yy*xx*cc
//now in worst case 6 queries else it takes only 4 in best case
//use this to optimize a bit
}
