#include "mars.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
int rep_[100000];
int min_row[100000];
int min_col[100001];
int fint(int v)
{
if(rep_[v] == v) return v;
rep_[v] = fint(rep_[v]);
return rep_[v];
}
void onion(int a, int b)
{
a = fint(a);
b = fint(b);
min_row[a] = min(min_row[a],min_row[b]);
min_col[a] = min(min_col[a],min_col[b]);
rep_[b] = a;
}
void upd(int** grid, int n, vi comps, int& ans, vi& ans_segs, int& zost)
{
rep(i,n)
{
rep(j,n)
{
int v = i*n+j;
min_col[v] = j;
min_row[v] = i;
rep_[v] = v;
}
}
vector<pii> segs;
pii prev = {n-1,2};
for(int i = n-1; i >= 3; i--)
{
if(grid[i][2] == 0)
{
if(!(prev.ff == i && prev.ss == 2))
{
rep2(k,prev.ff+1,i-1)
{
onion(k*n+2,(k+1)*n+2);
}
segs.pb(prev);
}
prev = {i-1,2};
}
}
for(int j = 2; j < n; j++)
{
if(grid[2][j] == 0)
{
if(!(prev.ff == 2 && prev.ss == j))
{
if(prev.ff == 2)
{
rep2(k,prev.ss+1,j-1)
{
onion(2*n+k,2*n+k-1);
}
}
else
{
rep2(k,prev.ff+1,2)
{
onion(k*n+2,(k+1)*n+2);
}
rep2(k,prev.ss+1,j-1)
{
onion(2*n+k,2*n+k-1);
}
}
segs.pb(prev);
}
prev = {2,j+1};
}
}
if(!(prev.ff== 2 && prev.ss == n))
{
rep2(k,prev.ss+1,n-1)
{
onion(2*n+k,2*n+k-1);
}
segs.pb(prev);
}
map<int,int> prev_same;
rep(j,n+3) prev_same[j] = -1;
int cur_sum = 0;
rep(i,siz(segs))
{
int com = comps[i];
if(com == 3)
{
continue;
}
if(com == 0)
{
if(prev_same[cur_sum] != -1) onion(segs[i].ff*n+segs[i].ss,prev_same[cur_sum]);
}
if(com == 1)
{
cur_sum++;
prev_same[cur_sum] = segs[i].ff*n+segs[i].ss;
}
if(com == 2)
{
onion(segs[i].ff*n+segs[i].ss,prev_same[cur_sum]);
prev_same[cur_sum] = -1;
cur_sum--;
}
}
vector<pii> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
rep(i,n)
{
rep(j,n)
{
forall(it,dirs)
{
int i2 = i+it.ff;
int j2 = j+it.ss;
if(i2 >= 0 && i2 <= n-1 && j2 >= 0 && j2 < n && grid[i][j] == 1 && grid[i2][j2] == 1)
{
onion(i*n+j,i2*n+j2);
}
}
}
}
set<int> rest;
rep(i,n)
{
rep(j,n)
{
if(fint(i*n+j) == i*n+j && grid[i][j] == 1)
{
int v = i*n+j;
if(min_col[v] != 0 && min_row[v] != 0) ans++;
else rest.insert(v);
}
}
}
zost = siz(rest);
segs = {};
prev = {n-1,0};
for(int i = n-1; i >= 1; i--)
{
if(grid[i][0] == 0)
{
if(!(prev.ff == i && prev.ss == 0))
{
segs.pb(prev);
}
prev = {i-1,0};
}
}
for(int j = 0; j < n; j++)
{
if(grid[0][j] == 0)
{
if(!(prev.ff == 0 && prev.ss == j))
{
segs.pb(prev);
}
prev = {0,j+1};
}
}
if(!(prev.ff == 0 && prev.ss == n))
{
segs.pb(prev);
}
set<int> was;
map<int,int> cnt;
map<int,int> cnt2;
forall(it,segs)
{
cnt[fint(it.ff*n+it.ss)]++;
cnt2[fint(it.ff*n+it.ss)]++;
}
stack<int> pop;
pop.push(-1);
forall(it,segs)
{
int v = fint(it.ff*n+it.ss);
cnt2[v]--;
if(cnt[v] == 1)
{
ans_segs.pb(3);
continue;
}
if(was.find(v) == was.end())
{
ans_segs.pb(1);
pop.push(v);
was.insert(v);
continue;
}
if(pop.top() == v && cnt2[v] != 0)
{
ans_segs.pb(0);
continue;
}
ans_segs.pb(2);
pop.pop();
}
}
string process(vector<vector<string>> a, int i, int j, int k, int n)
{
if(!(i == 2*(n-k-1) || j == 2*(n-k-1)))
{
string s;
rep(i,100) s += '0';
s[0] = a[0][0][0];
return s;
}
if(i == j)
{
string my_ans;
rep(i,100) my_ans += "0";
int prev_ans = 0;
rep2(i,90,99)
{
if(a[2][2][i] == '1') prev_ans += (1 << (i-90));
}
int** grid;
int d = k*2+3;
grid = new int*[d];
rep(i,d) grid[i] = new int[d];
rep(i,d) rep(j,d) grid[i][j] = 0;
grid[0][0] = (a[0][0][0] == '1' ? 1 : 0);
grid[1][0] = (a[1][0][0] == '1' ? 1 : 0);
grid[0][1] = (a[0][1][0] == '1' ? 1 : 0);
grid[1][1] = (a[1][1][0] == '1' ? 1 : 0);
vi coms;
rep3(i,0,88,2)
{
int v1 = (a[2][2][i] == '1' ? 1 : 0);
int v2 = (a[2][2][i+1] == '1' ? 1 : 0);
coms.pb(v1+v2*2);
}
if(k != 0)
{
int s = d;
rep2(i,2,d-1)
{
grid[i][0] = (a[2][0][i-2] == '1' ? 1 : 0);
}
rep2(i,2,d-1)
{
grid[i][1] = (a[2][1][i-2] == '1' ? 1 : 0);
}
rep2(i,2,d-1)
{
grid[i][2] = (a[2][1][i-2+s-2] == '1' ? 1 : 0);
}
rep2(i,2,d-1)
{
grid[0][i] = (a[0][2][i-2] == '1' ? 1 : 0);
}
rep2(i,2,d-1)
{
grid[1][i] = (a[1][2][i-2] == '1' ? 1 : 0);
}
rep2(i,2,d-1)
{
grid[2][i] = (a[1][2][i-2+s-2] == '1' ? 1 : 0);
}
}
else
{
rep(i,3)
{
rep(j,3)
{
grid[i][j] = (a[i][j][0] == '1' ? 1 : 0);
}
}
}
vi new_coms;
int zost;
upd(grid,d,coms,prev_ans,new_coms,zost);
if(k == n-1)
{
prev_ans += zost;
rep(bit,10)
{
if(prev_ans & (1 << bit))
{
my_ans[bit] = '1';
}
}
return my_ans;
}
rep(i,siz(new_coms))
{
int v1 = new_coms[i]%2;
int v2 = new_coms[i]/2;
if(v1 == 1) my_ans[i*2] = '1';
if(v2 == 1) my_ans[i*2+1] = '1';
}
rep2(bit,90,99)
{
if(prev_ans & (1 << (bit-90))) my_ans[bit] = '1';
}
return my_ans;
}
else if(i > j)
{
string a2;
int s = k*2+1;
a2 = a[0][0][0];
a2 += a[1][0][0];
rep(i,s) a2 += a[2][0][i];
a2 += a[0][1][0];
a2 += a[1][1][0];
rep(i,s)
{
a2 += a[2][1][i];
}
int d = 100-siz(a2);
rep(i,d) a2 += "0";
return a2;
}
else
{
string a2;
int s = k*2+1;
a2 = a[0][0][0];
a2 += a[0][1][0];
rep(i,s) a2 += a[0][2][i];
a2 += a[1][0][0];
a2 += a[1][1][0];
rep(i,s)
{
a2 += a[1][2][i];
}
int d = 100-siz(a2);
rep(i,d) a2 += "0";
return a2;
}
}
