#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
/*
20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
*/
int n;
int cost(int r1, int c1, int r2, int c2) { return n * n - (r2 - r1 + 1) * (c2 - c1 + 1) + 1; }
int ask(int r1, int c1, int r2, int c2) {
int cost1 = cost(r1, c1, r2, c2),
cost2 = cost(1, 1, n, n) + cost(r2 + 1, 1, n, n) + cost(1, c2 + 1, n, n) + cost(r2 + 1, c2 + 1, n, n);
if (cost1 < cost2)
return countTreasure(r1, c1, r2, c2);
else
return countTreasure(1, 1, n, n) - countTreasure(1, c2 + 1, n, n) - countTreasure(r2 + 1, 1, n, n) + countTreasure(r2 + 1, c2 + 1, n, n);
}
void findTreasure (int N) {
n = N;
int pref[n + 1][n + 1];
rep(i, 0, n + 1)
rep(j, 0, n + 1)
pref[i][j] = 0;
int ans[n][n];
rep(i, 1, n + 1)
rep(j, 1, n + 1) {
pref[i][j] = ask(1, 1, i, j);
ans[i][j] = pref[i][j] - pref[i - 1][j] - pref[i][j - 1] + pref[i - 1][j - 1];
}
rep(i, 1, n + 1)
rep(j, 1, n + 1)
if (ans[i][j])
Report(i, j);
}
