#include "treasure.h"
#include <iostream>
typedef struct nodet {
int y;
int x;
}node;
node q[100001] = { 0, };
int q_c = 0;
void go(int sy,int sx,int ey,int ex,int ret,int typ) {
//printf("%d %d %d %d %d %d\n", sy, sx, ey, ex, ret, typ);
if (sy == ey && sy == ey) {
q[q_c++] = { sy,sx };
//Report(sy, sx);
return;
}
if (typ == 0) {//x축으로 줄일것
int midx = (sx + ex) / 2;
int v = 0;
v = countTreasure(sy, sx, ey, midx);
if (v != 0) {
if (sx == midx) go(sy, sx, ey, midx, v,1);
else go(sy, sx, ey, midx, v, 0);
}
if (v == ret) return;
if ((midx+1) == ex) go(sy, midx + 1, ey, ex, ret - v, 1);
else go(sy, midx + 1, ey, ex, ret - v, 0);
}
else {//y축으로 줄일것
int midy = (sy + ey) / 2;
int v = 0;
v = countTreasure(sy, sx, midy, ex);
if (v != 0) {
go(sy, sx, midy, ex, v, 1);
}
if (v == ret) return;
go(midy+1, sx, ey, ex, ret - v, 1);
}
}
void findTreasure (int N) {
int cnt = countTreasure(1, 1, N, N);
if (cnt != 0) go(1, 1, N, N, cnt, 0);
for (int i = 0; i < q_c; i++) Report(q[i].y, q[i].x);
//if(cnt > 0) Report (1, 1);
}
