#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
int get_pos(vector<pair<int,int>>& A, int i, int j) {
return ranges::find(A, pair{i, j}) - A.begin();
}
vector<vector<int>> Azzurro(int n, int l, string s) {
s += string(51 - l, 'A');
vector<pair<int,int>> diag[15];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diag[i + j].emplace_back(i, j);
}
}
vector<vector<int>> G(n, vector<int>(n));
int p = 0;
for (int d = 0; d < 15; d++) {
if (diag[d].size() == 1) {
G[ diag[d][0].first ][ diag[d][0].second ] = s[p++] - 'A';
continue;
}
auto [si, sj] = diag[d][0];
for (int k = 1; k < diag[d].size(); k++) {
auto [i, j] = diag[d][k];
G[i][j] = s[p++] - 'A';
if (k % 2 == 0)
G[si][sj] ^= G[i][j];
}
}
return G;
}
// string Bordeaux(int n, int l, vector<vector<int>> G) {
// string s = string(1, 'B' - G[0][0]);
// vector<pair<int,int>> diag[15];
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// diag[i + j].emplace_back(i, j);
// }
// }
// int pi = 0, pj = 0;
// for (int d = 1; d < 15; d++) {
// int x = 0;
// for (int k = 0; k < diag[d].size(); k += 2) {
// auto [i, j] = diag[d][k];
// x ^= G[i][j];
// }
// int flip = x^1;
// int ni = pi, nj = pj;
// if (pi+1 < n && get_pos(diag[d], pi + 1, pj) % 2 == flip % 2) {
// ni++;
// } else {
// nj++;
// }
// for (int k = 1; k < diag[d].size(); k++) {
// auto [i, j] = diag[d][k];
// if (i == ni && j == nj) G[i][j] ^= 1;
// s += 'A' + G[i][j];
// }
// pi = ni, pj = nj;
// }
// s += 'B' - G[n-1][n-1];
// return s.substr(0, l);
// }
// int main() {
// int n = 8;
// int l = 3;
// for (int mask = 0; mask < 1 << l; mask++) {
// string s = string(l, 'A');
// for (int i = 0; i < l; i++)
// s[i] += (mask >> i & 1);
// auto G = Azzurro(n, l, s);
// for (int path = 0; path < 1 << 14; path++) {
// if (popcount(path) != 7) continue;
// int i = 0, j = 0;
// for (int k = 0; k < 14; k++) {
// G[i][j] ^= 1;
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// auto t = Bordeaux(n, l, G);
// if (s != t) {
// cout << s << " " << t << "\n";
// i = j = 0;
// for (int k = 0; k < 14; k++) {
// cout<<i<<' '<<j<<'\n';
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// return 1;
// }
// i = j = 0;
// for (int k = 0; k < 14; k++) {
// G[i][j] ^= 1;
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// }
// }
// }
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
int get_pos(vector<pair<int,int>>& A, int i, int j) {
return ranges::find(A, pair{i, j}) - A.begin();
}
// vector<vector<int>> Azzurro(int n, int l, string s) {
// s += string(51 - l, 'A');
// vector<pair<int,int>> diag[15];
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// diag[i + j].emplace_back(i, j);
// }
// }
// vector<vector<int>> G(n, vector<int>(n));
// int p = 0;
// for (int d = 0; d < 15; d++) {
// if (diag[d].size() == 1) {
// G[ diag[d][0].first ][ diag[d][0].second ] = s[p++] - 'A';
// continue;
// }
// auto [si, sj] = diag[d][0];
// for (int k = 1; k < diag[d].size(); k++) {
// auto [i, j] = diag[d][k];
// G[i][j] = s[p++] - 'A';
// if (k % 2 == 0)
// G[si][sj] ^= G[i][j];
// }
// }
// return G;
// }
string Bordeaux(int n, int l, vector<vector<int>> G) {
string s = string(1, 'B' - G[0][0]);
vector<pair<int,int>> diag[15];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diag[i + j].emplace_back(i, j);
}
}
int pi = 0, pj = 0;
for (int d = 1; d < 15; d++) {
int x = 0;
for (int k = 0; k < diag[d].size(); k += 2) {
auto [i, j] = diag[d][k];
x ^= G[i][j];
}
int flip = x^1;
int ni = pi, nj = pj;
if (pi+1 < n && get_pos(diag[d], pi + 1, pj) % 2 == flip % 2) {
ni++;
} else {
nj++;
}
for (int k = 1; k < diag[d].size(); k++) {
auto [i, j] = diag[d][k];
if (i == ni && j == nj) G[i][j] ^= 1;
s += 'A' + G[i][j];
}
pi = ni, pj = nj;
}
s += 'B' - G[n-1][n-1];
return s.substr(0, l);
}
// int main() {
// int n = 8;
// int l = 3;
// for (int mask = 0; mask < 1 << l; mask++) {
// string s = string(l, 'A');
// for (int i = 0; i < l; i++)
// s[i] += (mask >> i & 1);
// auto G = Azzurro(n, l, s);
// for (int path = 0; path < 1 << 14; path++) {
// if (popcount(path) != 7) continue;
// int i = 0, j = 0;
// for (int k = 0; k < 14; k++) {
// G[i][j] ^= 1;
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// auto t = Bordeaux(n, l, G);
// if (s != t) {
// cout << s << " " << t << "\n";
// i = j = 0;
// for (int k = 0; k < 14; k++) {
// cout<<i<<' '<<j<<'\n';
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// return 1;
// }
// i = j = 0;
// for (int k = 0; k < 14; k++) {
// G[i][j] ^= 1;
// (path >> k & 1) ? i++ : j++;
// }
// G[i][j] ^= 1;
// }
// }
// }
