#include "combo.h"

#include <bits/stdc++.h>
using namespace std;

vector<string> v;

string make(vector<int> id) {
        string res="";
        for(auto x:id) res+=v[x];
        return res;
}

string add(vector<string> S) {
        string res="";
        for(auto x:S) res+=x;
        return res;
}

string work() {
        if(press("AB")>0) {
                if(press("A")>0) {
                        return "A";
                } else {
                        return "B";
                }
        } else {
                if(press("X")>0) {
                        return "X";
                } else {
                        return "Y";
                }
        }
}

string work2(string s) {
        if(press(add({s,"A",s,"B"}))>s.size()) {
                if(press(add({s,"A"}))>s.size()) return add({s,"A"});
                return add({s,"B"});
        } 
        if(press(add({s,"X"}))>s.size()) return add({s,"X"});
        return add({s,"Y"});
}

std::string guess_sequence(int N) {
        string s=work();
        if(N==1) return s;

        set<string> S;
        S.insert("A");
        S.insert("B");
        S.insert("X");
        S.insert("Y");

        string t="";
        t+=s[0];
        S.erase(t);
        
        for(auto x:S) v.push_back(x);

        while(s.size()+2<=N) {
                int res;
                res=press(add({s,make({0,0}),s,make({0,1}),s,make({1,0})}));
                res-=s.size();

                if(res==0) {
                        s+=v[2];
                } else if(res==1) {
                        res=press(add({s,make({1,1})}));
                        res-=s.size();

                        if(res==0) s+=make({0,2});
                        else if(res==1) s+=make({1,2});
                        else if(res==2) s+=make({1,1});
                        else assert(false);

                } else if(res==2) {
                        res=press(add({s,make({0,0})}));
                        res-=s.size();

                        if(res==0) s+=make({1,0});
                        else if(res==1) s+=make({0,1});
                        else if(res==2) s+=make({0,0});
                        else assert(false);

                } else {
                        assert(false);
                }
        }

        if(s.size()<N) {
                return work2(s);
        }
        return s;
}