#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>
using namespace std;
int press(string p);
void fill(string &str, int l, int r, char c)
{
for(int i = l ; i <= r ; ++i)
{
str[i] = c;
}
}
void init(string &str, char c, int size)
{
str.resize(size);
for(int i = 0 ; i < size ; ++i)
{
str[i] = c;
}
}
string guess_sequence(int N)
{
string str, res;
init(res, '0', N);
char head = '0';
for(char symbol : {'A', 'B', 'X'})
{
init(str, symbol, N);
if(press(str) == 1)
{
head = symbol;
break;
}
}
if(head == '0')
{
head = 'Y';
}
std::vector<char> next;
for(char symbol : {'A', 'B', 'X', 'Y'})
{
if(symbol == head)
{
continue;
}
next.push_back(symbol);
}
res[0] = head;
for(int i = 1 ; i < N - 1 ; ++i)
{
init(str, '0', 4 * N);
for(int ptr = 0 ; ptr < 4 * N ; ptr += N)
{
for(int j = 0 ; j <= i - 1 ; ++j)
{
str[ptr + j] = res[j];
}
if(ptr == 0)
{
str[ptr + i] = next[0];
fill(str, ptr + i + 1, ptr + N - 1, head);
}
else if(ptr == N)
{
str[ptr + i] = next[1];
str[ptr + i + 1] = next[0];
fill(str, ptr + i + 2, ptr + N - 1, head);
}
else if(ptr == 2 * N)
{
str[ptr + i] = next[1];
str[ptr + i + 1] = next[1];
fill(str, ptr + i + 2, ptr + N - 1, head);
}
else
{
str[ptr + i] = next[1];
str[ptr + i + 1] = next[2];
fill(str, ptr + i + 2, ptr + N - 1, head);
}
}
int res_size = i - 1;
int prefix_size = press(str);
if(prefix_size == res_size + 1)
{
res[i] = next[0];
}
else if(prefix_size == res_size + 2)
{
res[i] = next[1];
}
else
{
assert(prefix_size == res_size);
res[i] = next[2];
}
}
char tail = '0';
for(char symbol : next)
{
init(str, '0', N);
for(int i = 0 ; i < N - 1 ; ++i)
{
str[i] = res[i];
}
str[N - 1] = symbol;
if(press(str) == N)
{
tail = symbol;
break;
}
}
if(tail == '0')
{
tail = next.back();
}
res[N - 1] = tail;
return res;
}
