#include "Azzurro.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pi pair<int, int>
namespace {
// グローバル変数と内部関数は無名名前空間内で宣言すること
// All global variables and internal functions should be declared in an unnamed namespace
int variable_example = 0;
int function_example(void) { return 0; }
}
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) {
vector<int> A;
for(int i=0; i<L; ++i) A.pb(S[i]=='A');
while(A.size() < 51) A.pb(1);
int idx = 0;
vector<vector<pi>> poss(2*N - 1);
for(int s=0; s<=2*N-2; ++s) {
for(int i=0; i<N; ++i) {
for(int j=0; j<N; ++j) {
if(i+j == s) {
poss[s].pb({i,j});
}
}
}
}
vector<int> sajz(2*N - 1);
for(int i=0; i<=2*N - 2; ++i) sajz[i] = (int)poss[i].size() - 1;
sajz[2*N - 3]++;
vector<vector<int>> R(N, vector<int>(N));
R[N-1][N-1] = A[50];
idx = 49;
for(int s=2*N - 3; s>=1; --s) {
int ksor = 0;
for(int i=sajz[s]-1; i>=0; --i) {
auto[r,c] = poss[s][i];
R[r][c] = A[idx];
--idx;
}
for(int i=0; i<(int)poss[s].size(); i+=2) {
auto[r,c] = poss[s][i];
ksor ^= R[r][c];
}
auto[r,c] = poss[s-1].back();
R[r][c] = ksor;
}
// for(int i=0; i<N; ++i) { for(int j=0; j<N; ++j) { cout << R[i][j]; } cout << "\n"; } cout << "\n";
return R;
}
#include "Bordeaux.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pi pair<int, int>
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 calc_ksor(vector<pi> pp, int sz, vector<vector<int>> &T) {
int ksor = 0;
for(int i=0; i<sz; i+=2) {
auto[r,c] = pp[i];
ksor ^= T[r][c];
}
return ksor;
}
}
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) {
vector<vector<pi>> poss(2*N - 1);
for(int s=0; s<=2*N-2; ++s) {
for(int i=0; i<N; ++i) {
for(int j=0; j<N; ++j) {
if(i+j == s) {
poss[s].pb({i,j});
}
}
}
}
vector<int> sajz(2*N - 1);
for(int i=0; i<=2*N - 2; ++i) sajz[i] = (int)poss[i].size() - 1;
sajz[2*N - 3]++;
T[0][0] ^= 1;
T[N-1][N-1] ^= 1;
vector<int> res;
int p1 = 0, p2 = 0;
int parity = T[0][0];
for(int s=1; s<=2*N - 3; ++s) {
int sz = poss[s].size();
int ok = 0;
if(p1 + 1 < N) {
p1++;
T[p1][p2] ^= 1;
if(calc_ksor(poss[s], poss[s].size(), T) != parity) {
T[p1][p2] ^= 1;
p1--;
} else ok++;
}
if(p2 + 1 < N && !ok) {
p2++;
T[p1][p2] ^= 1;
if(calc_ksor(poss[s], poss[s].size(), T) != parity) {
T[p1][p2] ^= 1;
p2--;
} else ok++;
}
for(int i=0; i<sajz[s]; ++i) {
auto[r,c] = poss[s][i];
res.pb(T[r][c]);
}
auto[r,c] = poss[s][sz-1];
parity = T[r][c];
}
res.pb(T[N-1][N-1]);
string s = "";
for(int i=0; i<L; ++i) {
if(res[i]) s.pb('A');
else s.pb('B');
}
return s;
}
