#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({2947667278772165694,
18301848765998365067,
729919693006235833,
11021831128136023278,
10003392056472839596,
1054412044467431918,
11649642299870863663,
7813497161378842344,
15536964167022953318,
16718309832681015833,
7805705913528825107,
12092317580524320504,
17163424360305231502,
6352792256529822470,
4696818759170745400,
8202730408965517889,
14576421520683731187,
12828242264541034313,
10287390044869019765,
5302155820127968924,
2689827791448149775,
10685535775509358833,
10414102509512663394,
2700937582377962954,
2770061463645390892,
10227015405405607450,
7160159996042967007,
4742464775291708339,
13980328397181907123,
2246378976408795298,
16851708943265217383});

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 = 31;

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({2947667278772165694,
18301848765998365067,
729919693006235833,
11021831128136023278,
10003392056472839596,
1054412044467431918,
11649642299870863663,
7813497161378842344,
15536964167022953318,
16718309832681015833,
7805705913528825107,
12092317580524320504,
17163424360305231502,
6352792256529822470,
4696818759170745400,
8202730408965517889,
14576421520683731187,
12828242264541034313,
10287390044869019765,
5302155820127968924,
2689827791448149775,
10685535775509358833,
10414102509512663394,
2700937582377962954,
2770061463645390892,
10227015405405607450,
7160159996042967007,
4742464775291708339,
13980328397181907123,
2246378976408795298,
16851708943265217383});

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 = 31;

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;
}