#include "Anna.h"

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

namespace anna {

mt19937_64 gen;

ull bexp(int i) {
	return 1ull << i;
}

bool get(ull a, int b) {
	return (a >> b)&1;
}

class basis {
public:
	vector<ull> vecs;
	basis() {
		vecs.assign(64, 0);
	}
	bool chk(ull v) {
		for (int i = 0; v && i < 64; i++) {
			if (get(v, i) == 0) continue;
			if (vecs[i] == 0) {
				return 1;
			}
			v ^= vecs[i];
		}
		return 0;
	}
	void ins(ull v) {
		for (int i = 0; v && i < 64; i++) {
			if (get(v, i) == 0) continue;
			if (vecs[i] == 0) {
				vecs[i] = v;
				return;
			}
			v ^= vecs[i];
		}
	}
};

vector<ull> full_basis({13980023449658672129, 4758477720936056390, 4767577253372562568, 9223516367117436434, 4767926904236327520, 74684338364599040, 13979193043492884610, 656410589309632, 146736699010598400, 83604673751515136, 9226194509008243328, 14053645650556454464, 13918392258094239298, 9442314508379932162, 9370801445437262848, 9233173367845572224, 13846461375025106048, 9297752078732558530, 4696010099225871490, 81769949948871360, 13844071164781119168, 228225356124392066, 4758361977707841664, 9376624461132336128, 9377714907862552130, 9228251955074813504, 14080879443417499200, 4659203906986345538, 515734727592887872, 14630303205004266624, 10448441306266552896, 16222184944347169344});

bool built = 0;
ull rows[8];
ull cols[8];
basis bases[8][8][8][8];

bool good(ull cur) {
	for (int i = 0; i < 8; i++) {
		for (int j = i+1; j < 8; j++) {
			for (int k = 0; k < 8; k++) {
				for (int l = k+1; l < 8; l++) {
					ull cmask = rows[i]|rows[j]|cols[k]|cols[l];
					if (!bases[i][j][k][l].chk(cur&(~cmask))) return 0;
				}
			}
		}
	}
	return 1;
}

void ins(ull cur) {
	for (int i = 0; i < 8; i++) {
		for (int j = i+1; j < 8; j++) {
			for (int k = 0; k < 8; k++) {
				for (int l = k+1; l < 8; l++) {
					ull cmask = rows[i]|rows[j]|cols[k]|cols[l];
					bases[i][j][k][l].ins(cur&(~cmask));
				}
			}
		}
	}
}

int max_basis = full_basis.size();

void build() {
	// gen = mt19937_64(0);
	// rows[0] = 255;
	// cols[0] = 0;
	// for (int i = 0; i < 8; i++) {
	// 	cols[0] |= bexp(8*i);
	// }
	// for (int i = 1; i < 8; i++) {
	// 	rows[i] = rows[i-1] << 8;
	// 	cols[i] = cols[i-1] << 1;
	// }
	// for (int i = 0; i < max_basis; i++) {
	// 	// cerr << "built " << i << '\n';
	// 	ull cur;
	// 	do {
	// 		cur = gen();
	// 	} while (!good(cur));
	// 	full_basis.push_back(cur);
	// 	ins(cur);
	// 	cerr << cur << '\n';
	// }
	built = 1;
}

}

void Anna(int x, int y, int n, string s) {
	if (!anna::built) anna::build();
	ull ans = 0;
	for (int i = 0; i < min(n, anna::max_basis); i++) {
		if (s[i] == 'B') ans ^= anna::full_basis[i];
	}
	for (int i = 0; i < 8; i++) {
		if (x == i) continue;
		for (int j = 0; j < 8; j++) {
			if (j == y) continue;
			Paint(i, j, anna::get(ans, 8*i+j));
		}
	}
	// for (int i = 0; i < 8; i++) {
	// 	for (int j = 0; j < 8; j++) {
	// 		if (i != X && j != Y) {
	// 			Paint(i, j, 0);
	// 		}
	// 	}
	// }
}

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

namespace bruno {

ull bexp(int i) {
	return 1ull << i;
}

bool get(ull a, int b) {
	return (a >> b)&1;
}

mt19937_64 gen;

class basis {
public:
	vector<ull> vecs;
	vector<ull> rep;
	basis() {
		vecs.assign(64, 0);
		rep.assign(64, 0);
	}
	bool chk(ull v) {
		for (int i = 0; v && i < 64; i++) {
			if (get(v, i) == 0) continue;
			if (vecs[i] == 0) {
				return 1;
			}
			v ^= vecs[i];
		}
		return 0;
	}
	void ins(ull v, int id = -1) {
		ull curv = (id == -1 ? 0 : bexp(id));
		for (int i = 0; v && i < 64; i++) {
			if (get(v, i) == 0) continue;
			if (vecs[i] == 0) {
				vecs[i] = v;
				rep[i] = curv;
				return;
			}
			v ^= vecs[i];
			if (id != -1) curv ^= rep[i];
		}
	}
	ull resolve(ull v) {
		ull ans = 0;
		for (int i = 0; v && i < 64; i++) {
			if (get(v, i) == 0) continue;
			assert(vecs[i]);
			v ^= vecs[i];
			ans ^= rep[i];
		}
		return ans;
	}
};

vector<ull> full_basis({13980023449658672129, 4758477720936056390, 4767577253372562568, 9223516367117436434, 4767926904236327520, 74684338364599040, 13979193043492884610, 656410589309632, 146736699010598400, 83604673751515136, 9226194509008243328, 14053645650556454464, 13918392258094239298, 9442314508379932162, 9370801445437262848, 9233173367845572224, 13846461375025106048, 9297752078732558530, 4696010099225871490, 81769949948871360, 13844071164781119168, 228225356124392066, 4758361977707841664, 9376624461132336128, 9377714907862552130, 9228251955074813504, 14080879443417499200, 4659203906986345538, 515734727592887872, 14630303205004266624, 10448441306266552896, 16222184944347169344});

bool built = 0;
ull rows[8];
ull cols[8];
basis bases[8][8][8][8];
basis fin_bases[8][8];

bool good(ull cur) {
	for (int i = 0; i < 8; i++) {
		for (int j = i+1; j < 8; j++) {
			for (int k = 0; k < 8; k++) {
				for (int l = k+1; l < 8; l++) {
					ull cmask = rows[i]|rows[j]|cols[k]|cols[l];
					if (!bases[i][j][k][l].chk(cur&(~cmask))) {
						return 0;
					}
				}
			}
		}
	}
	return 1;
}

void ins(ull cur, int id) {
	// for (int i = 0; i < 8; i++) {
	// 	for (int j = i+1; j < 8; j++) {
	// 		for (int k = 0; k < 8; k++) {
	// 			for (int l = k+1; l < 8; l++) {
	// 				ull cmask = rows[i]|rows[j]|cols[k]|cols[l];
	// 				bases[i][j][k][l].ins(cur&(~cmask));
	// 			}
	// 		}
	// 	}
	// }
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			ull cmask = rows[i]|cols[j];
			fin_bases[i][j].ins(cur&(~cmask), id);
		}
	}
}

int max_basis = full_basis.size();

void build() {
	gen = mt19937_64(0);
	rows[0] = 255;
	cols[0] = 0;
	for (int i = 0; i < 8; i++) {
		cols[0] |= bexp(8*i);
	}
	for (int i = 1; i < 8; i++) {
		rows[i] = rows[i-1] << 8;
		cols[i] = cols[i-1] << 1;
	}
	for (int i = 0; i < max_basis; i++) {
		// ull cur;
		// do {
		// 	cur = gen();
		// } while (!good(cur));
		// full_basis.push_back(cur);
		ins(full_basis[i], i);
	}
	built = 1;
}

}

string Bruno(int n, vector<vector<int>> arr) {
	if (!bruno::built) bruno::build();
	ull res = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) if (arr[i][j]) res += bruno::bexp(8*i+j);
	}
	ull ans = 0;
	bool f = 0;
	for (int i = 0; i < 8 && !f; i++) {
		for (int j = 0; j < 8 && !f; j++) {
			ull cmask = bruno::rows[i]|bruno::cols[j];
			if (!bruno::fin_bases[i][j].chk(res&(~cmask))) {
				ans = bruno::fin_bases[i][j].resolve(res&(~cmask));
				f = 1;
				break;
			}
		}
	}
	string sans = "";
	for (int i = 0; i < n; i++) {
		sans += char('A'+bruno::get(ans, i));
	}
	return sans;
}