#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<array<int, 2>> res;
void rec(int a, int b, int c, int d, int cnt) {
if (!cnt) {
return;
}
if (tie(a, b) == tie(c, d)) {
res.push_back({a, b});
return;
}
if (rng() % 2 && a != c) {
int m = (a + c) / 2;
int x = countTreasure(a, b, m, d);
if (x) {
rec(a, b, m, d, x);
}
if (x < cnt) {
rec(m + 1, b, c, d, cnt - x);
}
} else {
int m = (b + d) / 2;
int x = countTreasure(a, b, c, m);
if (x) {
rec(a, b, c, m, x);
}
if (x < cnt) {
rec(a, m + 1, c, d, cnt - x);
}
}
}
void findTreasure (int n) {
rec(1, 1, n, n, countTreasure(1, 1, n, n));
for (auto [x, y] : res) {
Report(x, y);
}
}
