#include "treasure.h"
#include<vector>
using namespace std;
typedef pair<int,int> pi;
vector<pi> ans;
void solve(int r1,int c1,int r2,int c2){
int cnt=countTreasure(r1,c1,r2,c2);
if(cnt==0) return ;
int sum=((r2-r1)+1)*((c2-c1)+1);
if(cnt<sum){
int mid1=(r1+r2)/2-1;
int mid2=(c1+c2)/2-1;
solve(r1,c1,r1,c1+mid2);
solve(r1,c1+mid2+1,r1,c2);
solve(r1+mid1+1,c1,r2,c1);
solve(r1+mid1+1,c1+mid2+1,r2,c2);
}
else{
for(int i=r1;i<=r2;i++){
for(int j=c1;j<=c2;j++){
ans.push_back({i,j});
}
}
}
return ;
}
void findTreasure (int N) {
solve(1,1,N,N);
for(auto next:ans){
Report(next.first,next.second);
}
}
