#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>;
vector<vector<int>> Azzurro(int n, int l, string s) {
assert(l <= 15);
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(8, vector<int>(8));
for (int d = 0; d < l; d++) {
char c = s[d];
if (diag[d].size() == 2) {
auto [i, j] = diag[d][0];
auto [x, y] = diag[d][1];
G[i][j] = 0;
G[x][y] = G[i][j] ^ (c - 'A');
continue;
}
for (auto [i, j] : diag[d]) {
G[i][j] = c - 'A';
}
}
return G;
}
#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>;
string Bordeaux(int n, int l, vector<vector<int>> G) {
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);
}
}
string t;
for (int d = 0; d < l; d++) {
if (diag[d].size() == 2) {
auto [i, j] = diag[d][0];
auto [x, y] = diag[d][1];
t += G[i][j] == G[x][y] ? 'B' : 'A';
continue;
}
int cnt[2]{};
for (auto [i, j] : diag[d]) {
cnt[G[i][j]]++;
}
int let = cnt[0] == 1;
t += 'A' + let;
}
return t;
}
