#include "mars.h"
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
pair<string, string> topairstr(vector<int> nums, string line) {
string opn(line.size(), '0'), cls(line.size(), '0');
int ind = 0;
map<int, int> lstps;
for (int i = 0; i < nums.size(); ++i) {
//cout << nums[i] << ' ';
if (line[i] == '1' and (i == 0 or line[i-1] != '1')) {
if (lstps.find(nums[i]) != lstps.end()) {
cls[ind] = '1';
opn[lstps[nums[i]]] = '1';
}
lstps[nums[i]] = ind;
ind++;
}
}
//cout << endl;
//cout << opn << endl << cls << endl << line << ' ' << "AMOG" << endl;
return {opn, cls};
}
vector<int> tovec(pair<string, string> ss, string line) {
auto [opn, cls] = ss;
vector<int> a(line.size());
vector<int> stk;
int nm = 0;
int ind = 0;
for (int i = 0; i < line.size(); ++i) {
if (line[i] == '1' and (i == 0 or line[i-1] != '1')) {
int thisnum;
if (cls[ind] == '1') {
thisnum = stk.back();
stk.pop_back();
} else {
thisnum = nm++;
}
a[i] = thisnum;
if (opn[ind] == '1')
stk.push_back(thisnum);
ind++;
} else if (line[i] == '1') {
a[i] = a[i - 1];
}
}
return a;
}
int getnuminstr(string a) {
int res = 0;
for (int i = 90; i < 100; ++i) {
res += (a[i] == '1') << (i - 90);
}
return res;
}
void chnuminstr(string &a, int res) {
for (int i = 90; i < 100; ++i) {
if (res & (1 << (i - 90)))
a[i] = '1';
else
a[i] = '0';
}
}
string get1str(string a) {
string b;
for (int i = 1; i < 45; ++i) {
b += a[i];
}
return b;
}
string get2str(string a) {
string b;
for (int i = 45; i < 90; ++i) {
b += a[i];
}
return b;
}
void ch1str(string &a, string b) {
for (int i = 1; i < 45; ++i) {
if (b.size() <= i - 1)
continue;
a[i] = b[i-1];
}
}
void ch2str(string &a, string b) {
for (int i = 45; i < 90; ++i) {
if (b.size() <= i - 45)
continue;
a[i] = b[i-45];
}
}
struct snm{
vector<int> p;
int cnt;
void init(int n) {
cnt = n;
p.assign(n, {});
for (int i = 0; i < n; ++i) {
p[i] = i;
}
}
int getv(int v) {
if (p[v] == v)
return v;
return p[v] = getv(p[v]);
}
void merge(int a, int b) {
a = getv(a);b = getv(b);
if (a != b) {
cnt--;
p[a] = b;
}
}
};
string resstring(string a) {
string s(100, '0');
for (int i = 90; i < 100; ++i) {
s[i-90] = a[i];
}
return s;
}
string solvepole(int n, vector<vector<string>> a, int iszero) {
vector<vector<int>> pole(n, vector<int>(n)), pole2(n, vector<int>(n, -1));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
pole[i][j] = a[i][j][0] - '0';
}
}
string si0 = get1str(a[2][0]);
string si1 = get1str(a[2][1]);
string si2 = get2str(a[2][1]);
string s0j = get1str(a[0][2]);
string s1j = get1str(a[1][2]);
string s2j = get2str(a[1][2]);
for (int i = 3; i < n; ++i) {
int pstr = n - 1 - i;
pole[i][0] = si0[pstr] - '0';
pole[i][1] = si1[pstr] - '0';
pole[i][2] = si2[pstr] - '0';
pole[0][i] = s0j[pstr] - '0';
pole[1][i] = s1j[pstr] - '0';
pole[2][i] = s2j[pstr] - '0';
}
//cout << a[2][2] << endl;
string opn = get1str(a[2][2]), cls = get2str(a[2][2]);
string zeroone;
for (int i = n - 1; i >= 2; --i) {
zeroone.push_back(pole[i][2] + '0');
}
for (int j = 3; j < n; ++j) {
zeroone.push_back(pole[2][j] + '0');
}
//cout << opn << endl;
//cout << cls << endl;
//cout << zeroone << endl;
vector<int> nums = tovec({opn, cls}, zeroone);
snm sm;
int res = getnuminstr(a[2][2]);
//cout << res << endl;
int sled = 0;
//cout << "NUMS ";
//for (auto i : nums)
// cout << i << ' ';
//cout << endl;
for (int i = 0; i < zeroone.size(); ++i) {
if (zeroone[i] == '1')
sled = max(sled, nums[i] + 1);
}
reverse(all(nums));
for (int i = n - 1; i >= 2; --i) {
if (pole[i][2] == 1) {
pole2[i][2] = nums.back();
}
nums.pop_back();
}
for (int j = 3; j < n; ++j) {
if (pole[2][j] == 1) {
pole2[2][j] = nums.back();
}
nums.pop_back();
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (pole[i][j] == 1) {
if (pole2[i][j] == -1) {
pole2[i][j] = sled++;
}
}
}
}
snm dsu;
dsu.init(sled);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (pole[i][j] == 1) {
if (i+1 != n and pole[i+1][j] == 1) {
dsu.merge(pole2[i][j], pole2[i+1][j]);
}
if (j+1 != n and pole[i][j+1] == 1) {
dsu.merge(pole2[i][j], pole2[i][j+1]);
}
}
}
}
res += dsu.cnt;
set<int> kr;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (pole[i][j]) {
pole2[i][j] = dsu.getv(pole2[i][j]);
if (i == 0 or j == 0)
kr.insert(pole2[i][j]);
}
}
}
if (!iszero)
res -= kr.size();
chnuminstr(a[0][0], res);
zeroone.clear();
nums.clear();
for (int i = n - 1; i >= 0; --i) {
zeroone.push_back(pole[i][0] + '0');
nums.push_back(pole2[i][0]);
}
for (int j = 1; j < n; ++j) {
zeroone.push_back(pole[0][j] + '0');
nums.push_back(pole2[0][j]);
}
if (iszero)
return resstring(a[0][0]);
auto [opn2, cls2] = topairstr(nums, zeroone);
ch1str(a[0][0], opn2);
ch2str(a[0][0], cls2);
return a[0][0];
}
string process(vector <vector<string>> a, int i, int j, int k, int n) {
if (((n - k - 1) * 2 + 1 > i and (n - k - 2) * 2 + 1 < i) or ((n - k - 1) * 2 + 1 > j and (n - k - 2) * 2 + 1 < j)) {
//cerr << i << ' ' << j << ' ' << k << endl;
if (i == j) {
string s = solvepole(2 * n + 1 - i, a, i == 0);
return s;
}
if (i < j) {
string s1 = get1str(a[0][2]);
string s2 = get2str(a[0][2]);
s1[2*(n-1)-j] = a[0][2][0];
s1[2*(n-1)-j+1] = a[0][1][0];
s2[2*(n-1)-j] = a[1][2][0];
s2[2*(n-1)-j+1] = a[1][1][0];
ch1str(a[0][0], s1);
ch2str(a[0][0], s2);
} else {
string s1 = get1str(a[2][0]);
string s2 = get2str(a[2][0]);
s1[2*(n-1)-i] = a[2][0][0];
s1[2*(n-1)-i+1] = a[1][0][0];
s2[2*(n-1)-i] = a[2][1][0];
s2[2*(n-1)-i+1] = a[1][1][0];
ch1str(a[0][0], s1);
ch2str(a[0][0], s2);
}
return a[0][0];
} else {
return a[0][0];
}
}
