#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> sol;
void solve(int xl, int xr, int yl, int yr, int total) {
if (xl == xr && yl == yr) {
sol.emplace_back(xl, yl);
return;
}
int lx = xr - xl, ly = yr - yl;
if (lx > ly) {
int mid = (xl + xr) / 2;
int t = countTreasure(xl, yl, mid, yr);
if (t != 0) {
solve(xl, mid, yl, yr, t);
}
if (t != total) {
solve(mid + 1, xr, yl, yr, total - t);
}
} else {
int mid = (yl + yr) / 2;
int t = countTreasure(xl, yl, xr, mid);
if (t != 0) {
solve(xl, xr, yl, mid, t);
}
if (t != total) {
solve(xl, xr, mid + 1, yr, t - total);
}
}
}
void findTreasure(int N) {
sol.clear();
int cnt = countTreasure(1, 1, N, N);
solve(1, N, 1, N, cnt);
for (auto& p : sol) {
Report(p.first, p.second);
}
}
