#include "combo.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
//#include <chrono>
//#include <random>
/*mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
string S;*/
//int press(string s) {
// int mx = 0;
// for (int i = 0; i < szof(s); i++) {
// string sub = "";
// for (int j = i; j < szof(s); j++) {
// sub += s[j];
// int pos = 0, siz = 0;
// while (pos < sub.size() && sub[pos] == S[pos]) {
// pos++, siz++;
// }
// mx = max(mx, siz);
// }
// }
// return mx;
//}
string get(string pref) {
if (press(pref + "A") == szof(pref) + 1) {
return "A";
}
else if (press(pref + "B") == szof(pref) + 1) {
return "B";
}
else if (press(pref + "X") == szof(pref) + 1) {
return "X";
}
else {
return "Y";
}
}
string guess_sequence(int n) {
string bad;
string s = get("");
bad = s;
if (n == 1) {
return s;
}
for (int i = 1; i <= n - 2; i++) { // we guess i + 1 character
//cout << i << ": " << s << endl;
int cost;
if (bad == "A") {
cost = press(s + "B" + s + "XY" + s + "XX" + s + "XB");
if (cost == szof(s)) {
s += 'Y';
}
if (cost == szof(s) + 1) {
s += 'B';
}
if (cost == szof(s) + 2) {
s += 'X';
}
}
if (bad == "B") {
cost = press(s + "A" + s + "XY" + s + "XX" + s + "XA");
if (cost == szof(s)) {
s += 'Y';
}
if (cost == szof(s) + 1) {
s += 'A';
}
if (cost == szof(s) + 2) {
s += 'X';
}
}
if (bad == "X") { // { A B Y }
cost = press(s + "A" + s + "BA" + s + "BB" + s + "BY");
if (cost == szof(s)) {
s += 'Y';
}
if (cost == szof(s) + 1) {
s += 'A';
}
if (cost == szof(s) + 2) {
s += 'B';
}
}
if (bad == "Y") { // { A B X }
cost = press(s + "A" + s + "BA" + s + "BB" + s + "BX");
if (cost == szof(s)) {
s += 'X';
}
if (cost == szof(s) + 1) {
s += 'A';
}
if (cost == szof(s) + 2) {
s += 'B';
}
}
}
s += get(s);
return s;
}
//signed main() {
// while (1) {
// S.clear();
// int n = rnd();
// n %= 100;
// S += 'A';
// for (int i = 2; i <= n; i++) {
// int x = rnd();
// if (x % 3 == 0) {
// S += 'B';
// }
// else if (x % 3 == 1) {
// S += 'X';
// }
// else {
// S += 'Y';
// }
// }
// if (S != guess_sequence(n)) {
// cout << S << " " << guess_sequence(n) << endl;
// exit(0);
// }
// }
//}
