#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
array<int,2>extract(string s){
assert(s.size()==100);
array<int,2>ans = {0,0};
for(int i = 70;i<100;i++){
if(s[i]=='1'){
ans[0]+=(1<<(i-70));
}
}
for(int i = 40;i<70;i++){
if(s[i]=='1'){
ans[1]+=(1<<(i-40));
}
}
return ans;
}
string put(string s, array<int,2>a){
assert(s.size()==100);
for(int i = 70;i<100;i++){
if(a[0]&(1<<(i-70))){
s[i]='1';
}
else{
s[i]='0';
}
}
for(int i = 40;i<70;i++){
if(a[1]&(1<<(i-40))){
s[i]='1';
}
else{
s[i]='0';
}
}
return s;
}
array<int,2> operator+(const array<int,2>&a, const array<int,2> &b){
return {a[0]+b[0],a[1]+b[1]};
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
int cor = 2*n-2-2*k;
//extract = {total land, joining pts}
if(i==cor||j==cor){
//to be consider
if(i==j){
//absolute corner
//must include data of all
array<int,2>tot = {0,0};
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
tot=tot+extract(a[i][j]);
}
}
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
tot[0]+=(a[i][j][0]=='1');
}
}
//all land considered
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
if(a[i][j][0]=='1'&&a[i][j+1][0]=='1'){
tot[1]++;
//this is a horizontal connector
}
if(a[i][j][0]=='1'&&a[i+1][j][0]=='1'&&(a[i+1][j+1][0]=='0'||a[i][j+1][0]=='0')){
//vertical connector
tot[1]++;
}
}
}
//everything for internal corners is done now.
//must do for cornermost corner
if(i==2*n-2){
//corner most corner. must include absolute edge as well
for(int i = 0;i<3;i++){
for(int j = 0;j<3;j++){
if(i==2||j==2){
tot[0]+=(a[i][j][0]=='1');
//land for corner included
}
if(i==2&&j!=2){
//bottom line
if(a[i][j][0]=='1'&&a[i][j+1][0]=='1'){
tot[1]++;
//horizontal connector
}
}
if(j==2&&i!=2){
if(a[i][j][0]=='1'&&a[i+1][j][0]=='1'){
tot[1]++;
//vertical connector(rightmost)
}
}
}
}
}
a[0][0]=put(a[0][0],tot);
}
else if(i==cor){
//bottom
array<int,2>tot = {0,0};
tot=extract(a[2][0]);
//others are 0
if(a[0][0][0]=='1'){
tot[0]++;
}
if(a[1][0][0]=='1'){
tot[0]++;
}
//land added
if(a[0][0][0]=='1'&&a[0][1][0]=='1'){
tot[1]++;
//horizontal connector
}
if(a[0][0][0]=='1'&&a[1][0][0]=='1'&&(a[0][1][0]=='0'||a[1][1][0]=='0')){
tot[1]++;
//vertical connector
}
if(a[1][0][0]=='1'&&a[1][1][0]=='1'){
tot[1]++;
//horizontal connector
}
if(a[1][0][0]=='1'&&a[2][0][0]=='1'&&(a[1][1][0]=='0'||a[2][1][0]=='0')){
tot[1]++;
//vertical connector
}
//added connectors
if(i==2*n-2){
//bottommost cor. must include 3rd layer also
if(a[2][0][0]=='1'){
tot[0]++;
//land
}
if(a[2][0][0]=='1'&&a[2][1][0]=='1'){
tot[1]++;
//horizontal connector
}
//vertical connector is impossible.
}
a[0][0]=put(a[0][0],tot);
}
else{
//rightmost
array<int,2>tot = {0,0};
tot=extract(a[0][2]);
//all others are 0s
if(a[0][0][0]=='1'){
tot[0]++;
}
if(a[0][1][0]=='1'){
tot[0]++;
}
//land added
if(a[0][0][0]=='1'&&a[0][1][0]=='1'){
tot[1]++;
//horizontal connector
}
if(a[0][1][0]=='1'&&a[0][2][0]=='1'){
tot[1]++;
//horizontal connector
}
if(a[0][0][0]=='1'&&a[1][0][0]=='1'&&(a[1][1][0]=='0'||a[0][1][0]=='0')){
tot[1]++;
//vertical connector
}
if(a[0][1][0]=='1'&&a[1][1][0]=='1'&&(a[1][2][0]=='0'||a[0][2][0]=='0')){
tot[1]++;
//vertical connecor
}
if(j==2*n-2){
//rightmost rig
//include rightmost also
if(a[0][2][0]=='1'){
tot[0]++;
}
//land added
if(a[0][2][0]=='1'&&a[1][2][0]=='1'){
tot[1]++;
//vertical connector
}
}
a[0][0]=put(a[0][0],tot);
}
if(cor==0){
//this is final stage
array<int,2>curr = extract(a[0][0]);
int ans = curr[0]-curr[1];
string fin(100,'0');
for(int i = 0;i<30;i++){
if((1<<i)&ans){
fin[i]='1';
}
}
a[0][0]=fin;
}
}
return a[0][0];
}
