#include "Azzurro.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>Azzurro(int n, int len, string s){
s += string(64, 'A');
vector<vector<int>>send(n, vector<int>(n, 0));
send[0][0] = s[0] == 'B';
const int MAXSUM = (n << 1) - 2;
int ptr = 1;
for(int sum = 1; sum < MAXSUM; sum++){
vector<pair<int, int>>a;
for(int x = 0; x < n; x++){
int y = sum - x;
if(y > -1 && y < n){
a.push_back(make_pair(x, y));
}
}
vector<bool>xv(2, false);
for(int i = 0; i + 1 < a.size(); i++){
if(s[ptr++] == 'B'){
send[a[i].first][a[i].second] = 1;
xv[i & 1] = !xv[i & 1];
}
}
send[a.back().first][a.back().second] = xv[1 - (int(a.size()) & 1)];
}
send[n - 1][n - 1] = s[ptr] == 'B';
return send;
}
#include "Bordeaux.h"
#include<bits/stdc++.h>
using namespace std;
string Bordeaux(int n, int len, vector<vector<int>>send){
string ans = "";
int px = 0, py = 0;
ans += 'A' + (send[0][0] ^ 1);
const int MAXSUM = (n << 1) - 2;
for(int sum = 1; sum < MAXSUM; sum++){
vector<pair<int, int>>a;
for(int x = 0; x < n; x++){
int y = sum - x;
if(y > -1 && y < n){
a.push_back(make_pair(x, y));
}
}
vector<bool>xv(2, false);
for(int i = 0; i + 1 < a.size(); i++){
if(send[a[i].first][a[i].second]){
xv[i & 1] = !xv[i & 1];
}
}
if(px == a.back().first || py == a.back().second){
if(xv[1 - (int(a.size()) & 1)] == send[a.back().first][a.back().second]){
tie(px, py) = a[int(a.size()) - 2];
}
else{
tie(px, py) = a.back();
}
}
else if(xv[1 - (int(a.size()) & 1)] == send[a.back().first][a.back().second]){
for(int i = int(a.size()) & 1; true; i += 2){
if(a[i].first == px || a[i].second == py){
tie(px, py) = a[i];
break;
}
}
}
else{
for(int i = 1 - (int(a.size()) & 1); true; i += 2){
if(a[i].first == px || a[i].second == py){
tie(px, py) = a[i];
break;
}
}
}
send[px][py] ^= 1;
for(int i = 0; i + 1 < a.size(); i++){
ans += 'A' + send[a[i].first][a[i].second];
}
}
ans += 'A' + (send[n - 1][n - 1] ^ 1);
return ans.substr(0, len);
}
