#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
vector<vector<int>> Azzurro(int n, int l, string s) {
if (l < 32)
s += string(32 - l, 'A');
vector<vector<int>> G(n, vector<int> (n));
int p = 0;
for (int i = 1; i < n; i += 2) {
for (int j = 0; j < n; j++) {
G[i][j] = s[p++] - 'A';
}
}
return G;
}
// string Bordeaux(int n, int l, vector<vector<int>> G) {
// string s;
// for (int i = 1; i < n; i += 2) {
// int t = n-1;
// while (G[i-1][t] == 0) t--;
// int b = 0;
// if (i == n-1) b = n-1;
// else while (G[i+1][b] == 0) b++;
// for (int j = 0; j < n; j++) {
// G[i][j] ^= t <= j && j <= b;
// s += 'A' + G[i][j];
// }
// }
// return s.substr(0, l);
// }
// int main() {
// int n = 8, l = 32;
// string s = "AB";
// while (s.size() < l) s += s;
// auto G = Azzurro(n, l, s);
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i == 0 || j == n-1) G[i][j] ^= 1;
// for (auto& r : G) {
// for (auto& x : r) cout<<x<<' ';
// cout<<"\n";
// }
// auto t = Bordeaux(n, l, G);
// cout << s << "\n" << t << "\n";
// }
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
// vector<vector<int>> Azzurro(int n, int l, string s) {
// if (l < 32)
// s += string(32 - l, 'A');
// vector<vector<int>> G(n, vector<int> (n));
// int p = 0;
// for (int i = 1; i < n; i += 2) {
// for (int j = 0; j < n; j++) {
// G[i][j] = s[p++] - 'A';
// }
// }
// return G;
// }
string Bordeaux(int n, int l, vector<vector<int>> G) {
string s;
for (int i = 1; i < n; i += 2) {
int t = n-1;
while (G[i-1][t] == 0) t--;
int b = 0;
if (i == n-1) b = n-1;
else while (G[i+1][b] == 0) b++;
for (int j = 0; j < n; j++) {
G[i][j] ^= t <= j && j <= b;
s += 'A' + G[i][j];
}
}
return s.substr(0, l);
}
// int main() {
// int n = 8, l = 32;
// string s = "AB";
// while (s.size() < l) s += s;
// auto G = Azzurro(n, l, s);
// for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i == 0 || j == n-1) G[i][j] ^= 1;
// for (auto& r : G) {
// for (auto& x : r) cout<<x<<' ';
// cout<<"\n";
// }
// auto t = Bordeaux(n, l, G);
// cout << s << "\n" << t << "\n";
// }
