#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define eb emplace_back
#define rep(x,y,z) for (int x=y;x<z;x++)
#include "Azzurro.h"
vector<vector<int>> Azzurro(int n, int l, string s) {
vector<vector<int>> a(n, vector<int>(n, 0));
while (s.size()<51) s.pb('0');
int idx=0;
rep(i,0,8){
rep(j,0,8){
if ((i==0&&j!=0)||(j==7&&i!=7)){
}else{
a[i][j]=(s[idx++]=='A');
}
}
}
rep(i,1,8){
int x=1,y=i-1; int par=0;
bool o=0;
while (x<n&&y>=0){
if (o) par+=a[x][y];
x++; y--; o=1-o;
} par%=2;
a[0][i]=par;
}
rep(i,1,7){
int x=i+1, y=7-1; int par=0;
bool o=0;
while (x<n&&y>=0){
if (o) par+=a[x][y];
x++; y--; o=1-o;
} par%=2;
a[i][7]=par;
}
return a;
}
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define eb emplace_back
#define rep(x,y,z) for (int x=y;x<z;x++)
#include "Bordeaux.h"
string Bordeaux(int n, int l, vector<vector<int>> a) {
// cout<<n<<"*\n";
vector<vector<bool>> pos(n,vector<bool>(n,0));
pos[0][0]=1;
function<bool(int,int)> val=[&](int i, int j){
return (0<=i&&i<n&&0<=j&&j<n);
};
vector<bool> v;
a[0][0]=1-a[0][0]; a[7][7]=1-a[7][7];
pos[0][1]=1; pos[1][0]=1;
rep(i,1,8){
int x=1,y=i-1,par=a[0][i];
bool o=0; int tot=0; int xx=-1, yy=-1;
if (pos[0][i]) xx=0,yy=i;
while (x<n&&y>=0){
if (pos[x][y]&&xx==-1) xx=x,yy=y;
if (o) tot+=a[x][y];
x++; y--; o=1-o;
} tot%=2;
int sx,sy;
if (xx==0){
if (tot!=par) sx=xx, sy=yy;
else sx=xx+1, sy=yy-1;
}else{
if ((tot!=par)^(xx%2==0)) sx=xx+1, sy=yy-1;
else sx=xx, sy=yy;
}
// cout<<0<<' '<<i<<' '<<sx<<' '<<sy<<'\n';
a[sx][sy]=1-a[sx][sy];
if (val(sx+1,sy)) pos[sx+1][sy]=1;
if (val(sx,sy+1)) pos[sx][sy+1]=1;
}
rep(i,1,7){
int x=i+1,y=7-1,par=a[i][7];
bool o=0; int tot=0; int xx=-1, yy=-1;
if (pos[i][7]) xx=i,yy=7;
while (x<n&&y>=0){
if (pos[x][y]&&xx==-1) xx=x,yy=y;
if (o) tot+=a[x][y];
x++; y--; o=1-o;
} tot%=2;
int sx,sy;
if (xx==i){
if (tot!=par) sx=xx, sy=yy;
else sx=xx+1, sy=yy-1;
}else{
if ((tot!=par)^((xx-i)%2==0)) sx=xx+1, sy=yy-1;
else sx=xx, sy=yy;
}
// cout<<i<<' '<<7<<' '<<tot<<' '<<par<<' '<<sx<<' '<<sy<<'\n';
a[sx][sy]=1-a[sx][sy];
if (val(sx+1,sy)) pos[sx+1][sy]=1;
if (val(sx,sy+1)) pos[sx][sy+1]=1;
}
string s;
rep(i,0,8){
rep(j,0,8){
if ((i==0&&j!=0)||(j==7&&i!=7)){
}else{
if (a[i][j]) s.pb('A');
else s.pb('B');
}
}
}
while (s.size()>l) s.pop_back();
return s;
}
