#include <bits/stdc++.h>
#include "treasure.h"
#define DIM 110
using namespace std;
int a[DIM][DIM];
int n,i,j;
/*int countTreasure (int x, int y, int x2, int y2){
cout<<x<<" "<<y<<" "<<x2<<" "<<y2<<endl;
int ans;
cin>>ans;
return ans;
}
void Report (int i, int j){
}
*/
void solve (int x, int y, int x2, int y2, int cnt){
if (x > x2 || y > y2 || !cnt)
return;
if (cnt == (x2-x+1) * (y2-y+1)){
for (int i=x;i<=x2;i++)
for (int j=y;j<=y2;j++)
a[i][j] = 1;
return;
}
int midx = (x+x2)>>1, midy = (y+y2)>>1, val1, val2, val3, val4;
val1 = countTreasure (x,y,midx,midy);
solve (x,y,midx,midy,val1);
if (midy+1 <= y2){
val2 = countTreasure (x,midy+1,midx,y2);
solve (x,midy+1,midx,y2,val2);
}
if (midx+1 <= x2){
val3 = countTreasure (midx+1,y,x2,midy);
solve (midx+1,y,x2,midy,val3);
}
if (midx+1 <= x2 && midy+1 <= y2){
val4 = cnt - val1 - val2 - val3;
solve (midx+1,midy+1,x2,y2,val4);
}
}
void findTreasure (int n) {
solve (1,1,n,n,countTreasure(1,1,n,n));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a[i][j])
Report (i,j);
/*cout<<"END\n";
for (i=1;i<=n;i++,cout<<"\n")
for (j=1;j<=n;j++)
cout<<a[i][j];
*/
}
