#include <bits/stdc++.h>
#include "grid_encoding.h"
using namespace std;

void send(vector<vector<int> > A) {
    int n=A.size();
    vector<int> X,Y;
    vector<pair<int,int> > a,b;
    for(int i=0;i<n;i++) {
        int cnt=0;
        for(int j=0;j<n;j++) cnt+=A[i][j];
        if(cnt) a.push_back({cnt,i});
        cnt=0;
        for(int j=0;j<n;j++) cnt+=A[j][i];
        b.push_back({cnt,i});
    }
    sort(a.begin(),a.end()),sort(b.begin(),b.end());
    reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
    for(auto i:a) X.push_back(i.second);
    for(auto i:b) Y.push_back(i.second);
    int lst=-1;
    for(int i=(int)X.size()-1;i>=0;i--) {
        for(int j=(int)Y.size()-1;j>=0;j--) {
            if(A[X[i]][Y[j]]==1) {
                if(i+1==X.size()) lst=j;
                else if(j==lst && j+1<Y.size()) {
                    select(X[i+1],Y[j+1]);
                    break;
                }
                select(X[i],Y[j]);
                break;
            }
        }
    }
    for(int i=(int)Y.size()-1;i>=0;i--) {
        for(int j=0;j<X.size();j++) {
            if(A[X[j]][Y[i]]==0) {
                select(X[j],Y[i]);
                break;
            }
        }
    }
}

vector<vector<int> > reconstruct(vector<vector<int> > B) {
    int n=B.size();
    vector<int> X,Y,visx(n),visy(n),cntx(n),cnty(n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(B[i][j]>=0) cntx[i]++,cnty[j]++;
    for(int i=0;i<n;i++) {
        int cnt=0;
        for(int j=0;j<n;j++) cnt+=B[j][i]>=0;
        if(!cnt) Y.push_back(i),visy[i]=1;
    }
    int x=-1,y=-1;
    for(int i=0;i<n;i++) {
        if(visy[i]) continue;
        int cnt=0,pos=-1;
        for(int j=0;j<n;j++) if(B[j][i]!=-1) cnt++,pos=j;
        if(cnt==1 && B[pos][i]==1) x=pos,y=i;
    }
    if(x==-1 && y==-1) {
        for(int i=0;i<n;i++) {
            if(cntx[i]!=1) continue;
            for(int j=0;j<n;j++) {
                if(visy[j]) continue;
                if(B[i][j]) x=i,y=j;
            }
        }
    }
    while(x!=-1 && y!=-1 && (!visx[x] || !visy[y])) {
        if(!visx[x]) X.push_back(x),visx[x]=1;
        if(!visy[y]) Y.push_back(y),visy[y]=1;
        pair<int,int> mn={1e9,1e9};
        for(int i=0;i<n;i++) {
            if(visy[i]) continue;
            if(B[x][i]>=0) mn=min(mn,{cnty[i],i});
        }
        if(mn.second!=1e9) {
            y=mn.second;
            continue;
        }
        for(int i=0;i<n;i++) {
            if(visx[i]) continue;
            if(B[i][y]>=0) mn=min(mn,{cntx[i],i});
        }
        if(mn.second!=1e9) {
            x=mn.second;
            continue;
        }
    }
    reverse(X.begin(),X.end());
    for(int i:X) {
        for(int j=(int)Y.size()-1,f=0;j>=0;j--) {
            if(B[i][Y[j]]==1) f=1;
            int now=B[i][Y[j]];
            B[i][Y[j]]=f;
            if(now==0 && j>0 && B[i][Y[j-1]]==-1) f=1;
        }
    }
    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;
}