#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
bool mat[MAXN + 1][MAXN + 1];
int cnt_c[MAXN + 1], cnt_l[MAXN + 1];
void findTreasure (int n) {
int i, j;
int last = countTreasure((n + 1) / 2 + 1, 1, n, n);
for(i = (n + 1) / 2; i >= 1; i--) {
cnt_l[i] = countTreasure(i, 1, n, n) - last;
last += cnt_l[i];
}
last = countTreasure(1, 1, (n + 1) / 2, n);
for(i = (n + 1) / 2 + 1; i <= n; i++) {
cnt_l[i] = countTreasure(1, 1, i, n) - last;
last += cnt_l[i];
}
last = countTreasure(1, (n + 1) / 2 + 1, n, n);
for(i = (n + 1) / 2; i >= 1; i--) {
cnt_c[i] = countTreasure(1, i, n, n) - last;
last += cnt_c[i];
}
last = countTreasure(1, 1, n, (n + 1) / 2);
for(i = (n + 1) / 2 + 1; i <= n; i++) {
cnt_c[i] = countTreasure(1, 1, n, i) - last;
last += cnt_c[i];
}
int sum_l = 0;
for(i = 1; i <= n; i++) {
sum_l += cnt_l[i];
}
for(i = 1; i <= (n + 1) / 2; i++) {
int cnt = 0, tot = 0, nr = 0;
for(j = 1; j < (n + 1) / 2; j++) {
int cur = countTreasure(i + 1, j + 1, n, n);
if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
mat[i][j] = 1;
tot++, nr++;
}
cnt += cnt_c[j];
}
cnt = nr = 0;
for(j = n; j > (n + 1) / 2; j--) {
int cur = countTreasure(i + 1, 1, n, j - 1);
if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
mat[i][j] = 1;
tot++, nr++;
}
cnt += cnt_c[j];
}
mat[i][(n + 1) / 2] = cnt_l[i] - tot;
for(j = 1; j <= n; j++) {
cnt_c[j] -= mat[i][j];
}
sum_l -= cnt_l[i];
}
/*for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
cerr << mat[i][j];
}
cerr << "\n";
}
cerr << "\n";*/
sum_l = 0;
for(i = 1; i <= n; i++) {
sum_l += cnt_l[i];
for(j = 1; j <= n; j++) {
cnt_c[j] += mat[i][j];
}
}
for(i = n; i > (n + 1) / 2; i--) {
int cnt = 0, tot = 0, nr = 0;
for(j = 1; j < (n + 1) / 2; j++) {
int cur = countTreasure(1, j + 1, i - 1, n);
if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
mat[i][j] = 1;
tot++, nr++;
}
cnt += cnt_c[j];
}
cnt = nr = 0;
for(j = n; j > (n + 1) / 2; j--) {
int cur = countTreasure(1, 1, i - 1, j - 1);
if(sum_l - cur - cnt < cnt_l[i] - nr + cnt_c[j]) {
mat[i][j] = 1;
tot++, nr++;
}
cnt += cnt_c[j];
}
mat[i][(n + 1) / 2] = cnt_l[i] - tot;
for(j = 1; j <= n; j++) {
cnt_c[j] -= mat[i][j];
}
sum_l -= cnt_l[i];
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
if(mat[i][j]) {
Report(i, j);
}
}
}
}
