#include <bits/stdc++.h>
using namespace std;
namespace {
vector<vector<int>> assemble(vector<vector<int>> base,int N){
assert(base.size()==2*N-1);
vector<vector<int>> x(N,vector<int>(N,0));
for(int round=0;round<2*N-1;round++){
if(round<N){
assert(base[round].size()==round+1);
for(int i=0;i<=round;i++){
x[i][round-i]=base[round][i];
}
} else {
int cnt = 2*N - round - 1;
assert(base[round].size()==cnt);
int inner = 0;
for(int i=round-N+1;i<N;i++){
x[i][round-i]=base[round][inner++];
}
}
}
return x;
};
}
vector<vector<int>> Azzurro(int N,int L,string S){
vector<vector<int>> base(2*N-1);
auto iter = S.begin();
auto getNext = [&](){
if(iter==S.end())return 0;
if((*iter++) == 'A')return 0;
return 1;
};
for(int i=0;i<2*N-1;i++){
if(i<N){
for(int j=0;j<i;j++)
base[i].emplace_back(getNext());
} else {
int cnt = 2*N - i - 2;
for(int j=0;j<cnt;j++)
base[i].emplace_back(getNext());
}
int XOR = 0;
for(int j=1;j<base[i].size();j+=2)XOR^=base[i][j];
base[i].emplace(base[i].begin(),XOR);
}
auto ans = assemble(base,N);
ans[0][0]=getNext();
ans[N-1][N-1]=getNext();
return ans;
}
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<vector<int>> dissemble(vector<vector<int>> x,int N){
vector<vector<int>> base(2*N-1);
for(int round=0;round<2*N-1;round++){
if(round<N){
for(int i=0;i<=round;i++){
base[round].emplace_back(x[i][round-i]);
}
} else {
int cnt = 2*N - round - 1;
for(int i=round-N+1;i<N;i++){
base[round].emplace_back(x[i][round-i]);
}
}
}
return base;
};
}
string Bordeaux(int N,int L,vector<vector<int>> T){
auto base = dissemble(T,N);
string s;
auto addNext = [&](int x){
if(x)s.push_back('B');
else s.push_back('A');
};
int oddViolater = 0;
int evenViolater = 0;
for(int i=0;i<2*N-1;i++){
int XOR = 0;
for(int j=0;j<base[i].size();j+=2)XOR^=base[i][j];
int violater = oddViolater;
if(XOR)violater = evenViolater;
base[i][violater]^=1;
for(int j=1;j<base[i].size();j++)addNext(base[i][j]);
oddViolater = violater;
evenViolater = violater+1;
if(i>=N-1){
evenViolater = violater-1;
}
if(evenViolater&1)swap(oddViolater,evenViolater);
}
addNext(T[0][0]^1);
addNext(T[N-1][N-1]^1);
s.resize(L);
return s;
}
