#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) {
vector<pair<int,int>> diag[60];
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;
}
// string Bordeaux(int n, int l, vector<vector<int>> G) {
// vector<pair<int,int>> diag[60];
// 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;
// }
// int main() {
// int n = 8, l = 15;
// string s = "AABBAABBAABBAAB";
// auto G = Azzurro(n, l, s);
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i == 0 || j == n-1) G[i][j] ^= 1;
// auto t = Bordeaux(n, l, G);
// for (auto& r : G) {
// for (auto& x : r) cout<<x<<' ';
// cout<<"\n";
// }
// cout << t << "\n";
// }
#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) {
// vector<pair<int,int>> diag[60];
// 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;
// }
string Bordeaux(int n, int l, vector<vector<int>> G) {
vector<pair<int,int>> diag[60];
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;
}
// int main() {
// int n = 8, l = 15;
// string s = "AABBAABBAABBAAB";
// auto G = Azzurro(n, l, s);
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i == 0 || j == n-1) G[i][j] ^= 1;
// auto t = Bordeaux(n, l, G);
// for (auto& r : G) {
// for (auto& x : r) cout<<x<<' ';
// cout<<"\n";
// }
// cout << t << "\n";
// }
