#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
vector<pi> ans;
int find(int y1,int x1,int y2,int x2){
int cnt=countTreasure(y1,x1,y2,x2);
if(x1==x2){
if(cnt==1){
ans.push_back(pi(y1,x1));
}
return cnt;
}
int size=(x2-x1+1)*(x2-x1+1);
int remain=cnt;
int y3=(y1+y2)>>1;
int x3=(x1+x2)>>1;
int pos[4][4]={{y1,x1,y3,x3},{y1,x3+1,y3,x2},{y3+1,x1,y2,x3},{y3+1,x3+1,y2,x2}};
for(int i=0;i<4;i++){
int *now=pos[i];
if(remain==size){
for(int j=now[0];j<=now[2];j++){
for(int k=now[1];k<=now[3];k++){
ans.push_back(pi(j,k));
}
}
remain-=(now[2]-now[0]+1)*(now[3]-now[1]+1);
}
else if(remain==0) break;
else{
remain-=find(now[0],now[1],now[2],now[3]);
}
size-=(now[2]-now[0]+1)*(now[3]-now[1]+1);
}
return cnt;
}
void findTreasure (int N) {
find(1,1,N,N);
for(auto i:ans){
Report(i.first,i.second);
}
}
