#include "treasure.h"
#include<vector>
using namespace std;
typedef pair<int, int> pi;
bool visit[107][107];
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++) {
if (visit[i][j]) continue;
visit[i][j] = true;
ans.push_back({ i,j });
}
}
}
return;
}
void findTreasure(int N) {
solve(1, 1, N, N);
for (auto next : ans) {
Report(next.first, next.second);
}
}
