#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 100;
int N;
int ans[MAXN+10][MAXN+10];
map<pair<pii, pii>, int> M;
int query(int y1, int x1, int y2, int x2)
{
if(y1>y2) swap(y1, y2);
if(x1>x2) swap(x1, x2);
if(M.find({{y1, x1}, {y2, x2}})!=M.end()) return M[{{y1, x1}, {y2, x2}}];
return M[{{y1, x1}, {y2, x2}}]=countTreasure(y1, x1, y2, x2);
}
void findTreasure(int _N)
{
N=_N;
int p=(N+1)/2;
for(int i=p+1; i<=N; i++) for(int j=p+1; j<=N; j++) ans[i][j]=query(1, 1, i, j)-query(1, 1, i-1, j)-query(1, 1, i, j-1)+query(1, 1, i-1, j-1);
for(int i=p-1; i>=1; i--) for(int j=p-1; j>=1; j--) ans[i][j]=query(i, j, N, N)-query(i+1, j, N, N)-query(i, j+1, N, N)+query(i+1, j+1, N, N);
for(int i=p+1; i<=N; i++) for(int j=p-1; j>=1; j--) ans[i][j]=query(i, j, 1, N)-query(i-1, j, 1, N)-query(i, j+1, 1, N)+query(i-1, j+1, 1, N);
for(int i=p-1; i>=1; i--) for(int j=p+1; j<=N; j++) ans[i][j]=query(i, j, N, 1)-query(i+1, j, N, 1)-query(i, j-1, N, 1)+query(i+1, j-1, N, 1);
for(int i=p+1; i<=N; i++)
{
int sum=0;
for(int j=1; j<p; j++) sum+=ans[j][i];
ans[p][i]=query(1, 1, p, i)-query(1, 1, p, i-1)-sum;
}
for(int i=p-1; i>=1; i--)
{
int sum=0;
for(int j=1; j<p; j++) sum+=ans[j][i];
ans[p][i]=query(1, N, p, i)-query(1, N, p, i+1)-sum;
}
for(int i=p+1; i<=N; i++)
{
int sum=0;
for(int j=1; j<p; j++) sum+=ans[i][j];
ans[i][p]=query(1, 1, i, p)-query(1, 1, i-1, p)-sum;
}
for(int i=p; i>=1; i--)
{
int sum=0;
for(int j=1; j<p; j++) sum+=ans[i][j];
ans[i][p]=query(N, 1, i, p)-query(N, 1, i+1, p)-sum;
}
for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(ans[i][j]) Report(i, j);
}
