#include "Azzurro.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
namespace {
// グローバル変数と内部関数は無名名前空間内で宣言すること
// All global variables and internal functions should be declared in an unnamed namespace
int variable_example = 0;
int function_example(void) { return 0; }
int c(char c){
if(c=='B')return 0;
else return 1;
}
}
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) {
std::vector<std::vector<int>> x(N, std::vector<int>(N, 0));
int n=N;
x[0][0]=c(S[0]);
for (int i=1;i<min(50, L);i++){
int tx=(i-1)/(n-1), ty=i%(n-1);
if (ty==0)ty+=(n-1);
//printf("i %d, tx %d, ty %d\n", i, tx, ty);
//cout<<S[i]<<" "<<c(S[i])<<endl;
x[tx][ty]=c(S[i]);
}
if(L == 51){
x[n-1][n-1] = c(S[L-1]);
}
/*for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<x[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
x[1][0]=0;
for(int i=0;i<n-1;i++){
for(int j=1;j<n;j++){
int tx,ty;
if(i+j < n)tx=i+j, ty=0;
else tx=n-1, ty=i+j-n+1;
if(i + j == 0 or i+j==2*n-2 or i+j==1 or i%2!=(tx)%2) continue;
x[tx][ty]^=x[i][j];
}
}
/*for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<x[i][j]<<" ";
}
cout<<endl;
}*/
return x;
}
#include "Bordeaux.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
namespace {
// グローバル変数と内部関数は無名名前空間内で宣言すること
// All global variables and internal functions should be declared in an unnamed namespace
int variable_example = 0;
int function_example(void) { return 0; }
int c(char c){
if(c=='B')return 0;
else return 1;
}
}
vector<pair<int,int>> dir={{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // R, D
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) {
int n=N;
/*cout<<endl;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout<<T[i][j]<<" ";
}
cout<<endl;
}*/
string ans;
vector<vector<int>> onpath(n+1, vector<int>(n+1, 0));
vector<int> xr(2*n+1, 0);
for(int i=0;i<n-1;i++){
for(int j=1;j<n;j++){
int tx,ty;
if(i+j < n)tx=i+j, ty=0;
else tx=n-1, ty=i+j-n+1;
if(i + j == 0 or i+j==2*n-2 or i+j==1 or i%2!=(tx)%2) continue;
xr[tx+ty]^=T[i][j];
}
}
for(int i=0;i<n;i++){
xr[i]^=T[i][0];
}
for(int j=1;j<n;j++){
xr[n-1+j]^=T[n-1][j];
}
/*for(int i=0;i<2*n-1;i++){
cout<<xr[i]<<" ";
}
cout<<endl;*/
onpath[0][0]=1, onpath[n-1][n-1]=1;
int x=0, y=1;
if(T[1][0]){
onpath[1][0]=1;
x=1, y=0;
}
while(!(x==n-1 and y == n-1)){
int tx,ty;
if(x+y+1 < n)tx=x+y+1, ty=0;
else tx=n-1, ty=x+y+1-n+1;
onpath[x][y]=1;
if(x==n-1){
y++;
continue;
}
if(y==n-1) {
x++;
continue;
}
if((x % 2==tx%2 and xr[x+y+1]!=0) or (x%2!=tx%2 and xr[x+y+1]==0))y++;
else x++;
}
if(T[0][0]) ans += 'B';
else ans += 'A';
for(int i=1;i<min(L,50);i++){
int x=(i-1)/(n-1), y=i%(n-1);
if(y==0)y+=(n-1);
if(onpath[x][y] ^ T[x][y]) ans += 'A';
else ans +='B';
}
if(L==51){
if(T[7][7]) ans += 'B';
else ans += 'A';
}
/*cout<<ans<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<onpath[i][j]<<" ";
}
cout<<endl;
}*/
return ans;
}
