#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 8;
int to[1 << N], from[1 << N];
void init() {
int cnt = 0;
for (int i = 0; i < (1 << N); i++) {
int cur = 0;
for (int j = 1; j < N; j += 2)
if (i & (1 << j))
cur ^= 1;
if (cur == 1) {
from[i] = -1;
continue;
}
to[cnt] = i;
from[i] = cnt++;
}
}
vector<vector<int>> Azzurro(int N, int L, string S) {
if (L > 40) return {};
while (L < 51) {
S.push_back('A');
L++;
}
vector<vector<int>> v(N, vector<int>(N, 0));
v[0][0] = S[0] - 'A';
v[7][7] = S[50] - 'A';
init();
int ptr = 1;
for (int s = 1; s <= 13; s++) {
int len = (s <= 7 ? s + 1 : 15 - s);
int msk = 0;
for (int i = 0; i < len - 1; i++)
msk |= ((S[ptr + i] - 'A') << i);
msk = to[msk];
for (int i = 0; i < 8; i++) {
int j = s - i;
if (j < 0 || j > 7) continue;
v[i][j] = (msk & 1);
msk >>= 1;
}
ptr += len - 1;
}
return v;
}
string Bordeaux(int N, int L, vector<vector<int>> v) {
init();
string S;
S.push_back((v[0][0] ^ 1) + 'A');
int x = 0, y = 0;
for (int s = 1; s <= 13; s++) {
int len = (s <= 7 ? s + 1 : 15 - s);
int x1 = x + 1, y1 = y;
int x2 = x, y2 = y + 1;
int msk1 = 0, msk2 = 0;
for (int i = 7; i >= 0; i--) {
int j = s - i;
if (j < 0 || j > 7) continue;
msk1 <<= 1;
msk1 |= (v[i][j] ^ (x1 == i && y1 == j));
msk2 <<= 1;
msk2 |= (v[i][j] ^ (x2 == i && y2 == j));
}
int msk = 0;
if (from[msk1] != -1 && 0 <= x1 && x1 <= 7 && 0 <= y1 && y1 <= 7) {
msk = msk1;
x = x1;
y = y1;
}
if (from[msk2] != -1 && 0 <= x2 && x2 <= 7 && 0 <= y2 && y2 <= 7) {
msk = msk2;
x = x2;
y = y2;
}
msk = from[msk];
for (int i = 0; i < len - 1; i++)
S.push_back(((msk >> i) & 1) + 'A');
}
S.push_back((v[7][7] ^ 1) + 'A');
while ((int) S.size() > L)
S.pop_back();
return S;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 8;
int to[1 << N], from[1 << N];
void init() {
int cnt = 0;
for (int i = 0; i < (1 << N); i++) {
int cur = 0;
for (int j = 1; j < N; j += 2)
if (i & (1 << j))
cur ^= 1;
if (cur == 1) {
from[i] = -1;
continue;
}
to[cnt] = i;
from[i] = cnt++;
}
}
vector<vector<int>> Azzurro(int N, int L, string S) {
if (L > 40) return {};
while (L < 51) {
S.push_back('A');
L++;
}
vector<vector<int>> v(N, vector<int>(N, 0));
v[0][0] = S[0] - 'A';
v[7][7] = S[50] - 'A';
init();
int ptr = 1;
for (int s = 1; s <= 13; s++) {
int len = (s <= 7 ? s + 1 : 15 - s);
int msk = 0;
for (int i = 0; i < len - 1; i++)
msk |= ((S[ptr + i] - 'A') << i);
msk = to[msk];
for (int i = 0; i < 8; i++) {
int j = s - i;
if (j < 0 || j > 7) continue;
v[i][j] = (msk & 1);
msk >>= 1;
}
ptr += len - 1;
}
return v;
}
string Bordeaux(int N, int L, vector<vector<int>> v) {
init();
string S;
S.push_back((v[0][0] ^ 1) + 'A');
int x = 0, y = 0;
for (int s = 1; s <= 13; s++) {
int len = (s <= 7 ? s + 1 : 15 - s);
int x1 = x + 1, y1 = y;
int x2 = x, y2 = y + 1;
int msk1 = 0, msk2 = 0;
for (int i = 7; i >= 0; i--) {
int j = s - i;
if (j < 0 || j > 7) continue;
msk1 <<= 1;
msk1 |= (v[i][j] ^ (x1 == i && y1 == j));
msk2 <<= 1;
msk2 |= (v[i][j] ^ (x2 == i && y2 == j));
}
int msk = 0;
if (from[msk1] != -1 && 0 <= x1 && x1 <= 7 && 0 <= y1 && y1 <= 7) {
msk = msk1;
x = x1;
y = y1;
}
if (from[msk2] != -1 && 0 <= x2 && x2 <= 7 && 0 <= y2 && y2 <= 7) {
msk = msk2;
x = x2;
y = y2;
}
msk = from[msk];
for (int i = 0; i < len - 1; i++)
S.push_back(((msk >> i) & 1) + 'A');
}
S.push_back((v[7][7] ^ 1) + 'A');
while ((int) S.size() > L)
S.pop_back();
return S;
}
