#include "grid_encoding.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=507;
const ll J=1e18;
int n,sh[N],sw[N],hh[N],ww[N];
void send(std::vector<std::vector<int>> A) {
	n=A.size();
	for (int i=0;i<n;i++) sh[i]=sw[i]=0;
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) sh[i]+=A[i][j],sw[j]+=A[i][j];
	iota(hh,hh+n,0),sort(hh,hh+n,[](int x,int y){return sh[x]>sh[y];});
	iota(ww,ww+n,0),sort(ww,ww+n,[](int x,int y){return sw[x]>sw[y];});
	for (ll i=0,j=n-1;i<n;i++) {
		select(hh[i],ww[j]);
		while (j>=max(i==n-1?1:sh[hh[i]],1)) select(hh[i],ww[--j]);
	}
}
vector<pii> e[N][N];
vector<int> v[N];
std::vector<std::vector<int>> reconstruct(std::vector<std::vector<int>> B) {
	n=B.size();
	for (int i=0;i<n;i++) {
		sh[i]=sw[i]=0;
		for (int j=0;j<n;j++) e[i][j].clear();
	}
	int cnt[2]={0,0};
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (B[i][j]!=-1) cnt[B[i][j]]++;
	if (!cnt[0]||!cnt[1]) {
		int x=cnt[0]==0;
		for (int i=0;i<n;i++) for (int j=0;j<n;j++) B[i][j]=x;
	}
	else {
		for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (B[i][j]!=-1) sh[i]++,sw[j]++;
		auto add=[&](int xa,int ya,int xb,int yb){
			// cerr<<xa<<" "<<ya<<" "<<xb<<" "<<yb<<"\n";
			e[xa][ya].pb({xb,yb}),e[xb][yb].pb({xa,ya});};
		for (int i=0;i<n;i++) {
			vector<int> st,tp;
			for (int j=0;j<n;j++) if (B[i][j]!=-1) {
				if (sw[j]>=2) st.pb(j);
				else tp.pb(j);
			}
			tp.insert(tp.begin(),st[0]);
			if (st.size()==2) tp.pb(st[1]);
			for (int j=1;j<tp.size();j++) add(i,tp[j-1],i,tp[j]);
		}
		for (int i=0;i<n;i++) {
			vector<int> st,tp;
			for (int j=0;j<n;j++) if (B[j][i]!=-1) {
				if (sh[j]>=2) st.pb(j);
				else tp.pb(j);
			}
			sort(tp.begin(),tp.end(),[&](int x,int y){return B[x][i]>B[y][i];});
			if (st.size()) {
				tp.insert(tp.begin(),st[0]);
				if (st.size()==2) tp.pb(st[1]);
			}
			// printf("%d: ",i); for (int j:tp) printf(" %d",j); printf("\n");
			for (int j=1;j<tp.size();j++) add(tp[j-1],i,tp[j],i);
		}
		auto get=[&](int x,int y,pii z) {
			int i=x,j=y;
			while (i==x) {
				v[x].pb(j); int flg=1;
				for (pii k:e[i][j]) if (k!=z) { z={i,j},i=k.fi,j=k.se,flg=0; break; }
				if (flg) return pii{0,0};
			}
			return pii{i,j};
		};
		int flgg=1;
		for (int i=0;i<n&&flgg;i++) for (int j=0;j<n;j++) if (e[i][j].size()==1) {
			// cerr<<"  "<<i<<" "<<j<<"\n";
			pii x={i,j},y,lst={-1,-1}; int flg=1,has=0; vector<int> vv;
			for (int k=0;k<n;k++) {
				v[x.fi].clear();
				y=get(x.fi,x.se,lst);
				// printf("%d ",x.fi); for (int i:v[x.fi]) printf(" %d",i); printf("\n");
				if (!B[x.fi][v[x.fi][0]]&&(B[x.fi][v[x.fi].back()]||has)) { flg=0; break; }
				for (int l:v[x.fi]) has|=B[x.fi][l];
				lst={x.fi,v[x.fi].back()},vv.pb(x.fi),x=y;
			}
			if (flg) {
				// cerr<<i<<" "<<j<<"\n";
				vector<int> now;
				for (int i=0;i<n;i++) {
					int j=0;
					while (j<v[vv[i]].size()&&B[vv[i]][v[vv[i]][j]]) now.pb(v[vv[i]][j++]);
					for (int k:now) B[vv[i]][k]=1;
					while (j+1<v[vv[i]].size()) now.pb(v[vv[i]][j++]);
				}
				flgg=0; break;
			}
		}
		for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (B[i][j]==-1) B[i][j]=0;
	}
	return B;
}