#include "mars.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
// 1 bit -> value of this cell
// 10 bit -> number of islands in binary
// 40 bit -> value of cells on right
// 40 bit -> value of cell on down
int calc(vector <vector <char>> v) {
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n = v.size(), m = v[0].size();
int res = 0;
vector <vector <char>> col(n, vector <char>(m, 0));
for (int ux = 0; ux < n; ux++) {
for (int uy = 0; uy < m; uy++) {
if (v[ux][uy] == '0') {
continue;
}
if (col[ux][uy]) continue;
queue <pair<int, int>> q;
q.push({ux, uy});
col[ux][uy] = 1;
res++;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int z = 0; z < 4; z++) {
int i = x + dx[z], j = y + dy[z];
if (i < 0 || j < 0 || i >= n || j >= m) continue;
if (v[i][j] == '0') continue;
if (col[i][j]) continue;
col[i][j] = 1;
q.push({i, j});
}
}
}
}
cerr << "\nIn build: " << res << endl;
return res;
}
char get(int i, int j, string x, int a, int b) {
if (i == a && j == b) {
return x[0];
}
if (i == a) {
int k = b - j;
return x[k + 10];
}
if (j == b) {
int k = a - i;
return x[k + 50];
}
else {
cerr << "Nah bro..." << endl;
}
return '0';
}
int num(string x) {
int res = 0, k=1;
for (int i = 1; i <= 10; i++) {
res += (x[i] - '0') * k;
k *= 2;
}
return res;
}
string f(int x, string a, string b) {
string ans(100, '0');
for (int i = 1; i <= 10; i++) {
if (x & (1 << (i - 1))) ans[i] = '1';
else ans[i] = '0';
}
for (int i = 11; i <= 50; i++) {
if (i - 11 >= a.size()) break;
ans[i] = a[i - 11];
}
for (int i = 51; i <= 90; i++) {
if (i - 51 >= b.size()) break;
ans[i] = b[i - 51];
}
return ans;
}
string build1(int m, int i, int j, string a, string b) {
int res = num(b);
string c, d;
for (int z = j+1; z < m; z++) {
c.pb(get(i, j+1, a, i, z));
d.pb(get(i+1, j+1, b, i+1, z));
}
vector <pair<int, int>> v;
int ls = -1;
for (int z = 0; z < c.size(); z++) {
if (c[z] == '1') {
if (ls == -1) ls = z;
}
else {
if (ls != -1) {
v.pb({ls, z-1});
ls = -1;
}
}
}
if (ls != -1) v.pb({ls, c.size()-1});
for (auto [l, r] : v) {
bool ok = 1;
for (int z = l; z <= r; z++) {
if (d[z] == '1') {
ok = 0;
break;
}
}
if (ok) res++;
}
return f(res, c, "");
}
string build2(int m, int i, int j, string a, string b) {
int res = num(b);
string c, d;
for (int z = i + 1; z < m; z++) {
c.pb(get(i+1, j, a, z, j));
d.pb(get(i+1, j+1, b, z, j+1));
}
vector <pair<int, int>> v;
int ls = -1;
for (int z = 0; z < c.size(); z++) {
if (c[z] == '1') {
if (ls == -1) ls = z;
}
else {
if (ls != -1) {
v.pb({ls, z-1});
ls = -1;
}
}
}
if (ls != -1) v.pb({ls, c.size()-1});
for (auto [l, r] : v) {
bool ok = 1;
for (int z = l; z <= r; z++) {
if (d[z] == '1') {
ok = 0;
break;
}
}
if (ok) res++;
}
return f(res, "", c);
}
string process(vector <vector<string>> g, int i, int j, int k, int n) {
cerr << "Next one" << k << ' ' << i << ' ' << j << endl;
if (n == 1) {
vector <vector <char>> v;
for (auto z : g) {
vector <char> v1;
for (auto z1 : z) v1.pb(z1[0]);
v.pb(v1);
}
int res = calc(v);
string ans(100, '0');
for (int i = 0; i < 10; i++) {
if (res & (1 << i)) ans[i] = '1';
}
return ans;
}
if (i != 2 * (n - k - 1) && j != 2 * (n - k - 1)) return g[0][0];
int m = 2 * n + 1;
string cc, dd;
if (i == 2 && j == 2) {
string c;
c.pb(g[1][1][0]);
c.pb(g[2][1][0]);
for (int z = 51; z <= 88; z++) {
c.pb(g[2][1][z]);
}
cc = c;
}
if (i == 0 && j == 2) {
dd.pb(g[0][1][0]);
dd.pb(g[1][1][0]);
dd.pb(g[2][1][0]);
}
if (k == 0) {
cerr << 'x';
if (i < j) {
cerr << 'a' << endl;
vector <vector <char>> v;
for (auto z : g) {
vector <char> v1;
for (auto z1 : z) v1.pb(z1[0]);
v.pb(v1);
}
cerr << 'b' << endl;
string c = to_string(v[1][0] - '0');
c += v[2][0];
string ans = f(calc(v), c, "");
cerr << 'c' << endl;
ans[0] = g[0][0][0];
if (i == 0 && j == 2) {
for (int z = 0; z < dd.size(); z++) ans[z + 51] = dd[z];
}
return ans;
}
if (i >= j) {
cerr << "Its going to down!!!\n";
vector <vector <char>> v;
for (auto z : g) {
vector <char> v1;
for (auto z1 : z) v1.pb(z1[0]);
v.pb(v1);
}
cerr << 'b';
string c = to_string(v[0][1] - '0');
c += v[0][2];
cerr << 'd';
string ans = f(calc(v), "", c);
cerr << 'c';
ans[0] = g[0][0][0];
if (i == 2 && j == 2) {
for (int z = 11; z <= 50; z++) ans[z] = cc[z-11];
}
return ans;
}
}
if (i < j) {
string a = build1(m, i, j+1, g[0][2], g[1][2]);
a[0] = g[0][1][0];
string b = build2(m, i+1, j+1, g[1][2], g[2][2]);
b[0] = g[1][1][0];
string ans = build1(m, i, j, a, b);
ans[0] = g[0][0][0];
if (i == 0 && j == 2) {
for (int z = 0; z < dd.size(); z++) ans[z + 51] = dd[z];
}
return ans;
}
if (i > j || (i == j && k != n - 1)) {
string a = build2(m, i+1, j, g[2][0], g[2][1]);
a[0] = g[1][0][0];
string b = build2(m, i+1, j+1, g[2][1], g[2][2]);
b[0] = g[1][1][0];
string ans = build2(m, i, j, a, b);
ans[0] = g[0][0][0];
if (i == 2 && j == 2) {
for (int z = 11; z <= 50; z++) ans[z] = cc[z-11];
}
return ans;
}
vector <vector <char>> v(m, vector <char>(4, '0'));
for (int z1 = 0; z1 < 3; z1++) {
for (int z2 = 0; z2 < 3; z2++) {
v[z1][z2] = g[z1][z2][0];
}
}
for (int z = 3; z < m; z++) {
v[z][0] = get(2, 0, g[2][0], z, 0);
v[z][1] = get(2, 1, g[2][1], z, 1);
v[z][2] = get(2, 2, g[2][2], z, 2);
}
for (int z = 51; z <= 53; z++) {
v[z-51][3] = g[0][2][z];
}
for (int z = 11; z <= 50; z++) {
if (z - 8 >= m) break;
v[z-8][3] = g[2][2][z];
}
int res = num(g[0][2]);
cerr << "\nResult: " << res << endl;
for (int s = 2; s >= 0; s--) {
vector <pair<int, int>> e;
int ls = -1;
for (int z = 0; z < v.size(); z++) {
if (v[z][s+1] == '1') {
if (ls == -1) ls = z;
}
else {
if (ls != -1) {
e.pb({ls, z-1});
ls = -1;
}
}
}
if (ls != -1) e.pb({ls, m - 2});
for (auto [l, r] : e) {
bool ok = 1;
for (int z = l; z <= r; z++) {
if (v[z][s] == '1') {
ok = 0;
break;
}
}
if (ok) res++;
}
}
for (int z1 = 0; z1 < m; z1++) {
for (int z2 = 0; z2 < 4; z2++) cerr << v[z1][z2] << ' ';
cerr << endl;
}
string ans(100, '0');
for (int i = 0; i < 10; i++) {
if (res & (1 << i)) ans[i] = '1';
}
return ans;
}
/*
1
2
1 1 0 1 0
0 0 1 1 0
1 0 0 1 0
1 1 1 1 1
0 0 0 0 0
1
3
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
*/
