#include <bits/stdc++.h>
#include "treasure.h"
using namespace std;
typedef pair<int, int> ii;
map<pair<ii, ii>, int> mp;
int grid[101][101], vis[101][101], n;
int ask(int x1, int y1, int x2, int y2) {
if(x1 > x2 || y1 > y2) return 0;
pair<ii, ii> key = {{x1, y1}, {x2, y2}};
if(!mp.count(key)) mp[key] = countTreasure(x1, y1, x2, y2);
return mp[key];
}
int get(int x1, int y1, int x2, int y2) {
if(x1 > x2 || y1 > y2) return 0;
pair<ii, ii> key = {{x1, y1}, {x2, y2}};
if(mp.count(key)) return 0;
return 1 + n * n - (x2 - x1 + 1) * (y2 - y1 + 1);
}
int solve(int i, int j) {
int op11 = get(1, 1, i, j) + get(1, 1, i - 1, j) + get(1, 1, i, j - 1) + get(1, 1, i - 1, j - 1);
int opnn = get(i, j, n, n) + get(i, j + 1, n, n) + get(i + 1, j, n, n) + get(i + 1, j + 1, n, n);
int op1n = get(1, j, i, n) + get(1, j, i - 1, n) + get(1, j + 1, i, n) + get(1, j + 1, i - 1, n);
int opn1 = get(i, 1, n, j) + get(i, 1, n, j - 1) + get(i + 1, 1, n, j) + get(i + 1, 1, n, j - 1);
int mn = min({op11, opnn, op1n, opn1});
if(op11 == mn) {
return ask(1, 1, i, j) - ask(1, 1, i - 1, j) - ask(1, 1, i, j - 1) + ask(1, 1, i - 1, j - 1);
} else if(opnn == mn) {
return ask(i, j, n, n) - ask(i, j + 1, n, n) - ask(i + 1, j, n, n) + ask(i + 1, j + 1, n, n);
} else if(op1n == mn) {
return ask(1, j, i, n) - ask(1, j, i - 1, n) - ask(1, j + 1, i, n) + ask(1, j + 1, i - 1, n);
} else {
return ask(i, 1, n, j) - ask(i, 1, n, j - 1) - ask(i + 1, 1, n, j) + ask(i + 1, 1, n, j - 1);
}
}
void findTreasure (int N) { n = N;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(n & 1) {
if(i == (n + 1) / 2 || j == (n + 1) / 2) continue;
} else {
if(i == n / 2 || i == n / 2 + 1 || j == n / 2 || j == n / 2 + 1) continue;
}
vis[i][j] = 1;
grid[i][j] = solve(i, j);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(!vis[i][j]) grid[i][j] = solve(i, j);
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(grid[i][j]) Report(i, j);
}
}
}
