#include "treasure.h"
int ps1[105][105];
int ps2[105][105];
int ps3[105][105];
int ps4[105][105];
int exist[105][105];
int memo[101][101][101][101];
int _f(int l, int r, int d, int u){
int& t=memo[l][r][d][u];
if(!t) t = countTreasure(l, r, d, u) + 1;
return t-1;
}
#define countTreasure _f
void s1(int N, int n, int m){
if(m+1 <= N)
for(int i=1; i<=n; ++i) ps1[i][m+1] = countTreasure(i, m+1, N, N);
if(n+1 <= N)
for(int i=1; i<=m; ++i) ps1[n+1][i] = countTreasure(n+1, i, N, N);
if(n+1 <= N && m+1 <= N)
ps1[n+1][m+1] = countTreasure(n+1, m+1, N, N);
for(int i=n; 1<=i; --i){
for(int j=m; 1<=j; --j){
int t = countTreasure(i, j, N, N);
ps1[i][j] = t;
exist[i][j] = t - ps1[i+1][j] - ps1[i][j+1] + ps1[i+1][j+1];
}
}
}
#include <cstdio>
void s2(int N, int n, int m){
int bot = 0;
if(n+1 <= N && 1 <= m-1){
bot = countTreasure(n+1, 1, N, m-1);
ps2[n+1][m-1] = bot;
}
for(int i=n; 1<=i; --i){
for(int j=1; j<m; ++j){
ps2[i][j] = ps2[i+1][j] + ps2[i][j-1] - ps2[i+1][j-1] + exist[i][j];
}
}
if(n+1 <= N)
for(int i=m; i<=N; ++i) ps2[n+1][i] = countTreasure(n+1, 1, N, i);
for(int i=n; 1<=i; --i){
for(int j=m; j<=N; ++j){
int t = countTreasure(i, 1, N, j);
ps2[i][j] = t;
exist[i][j] = t - ps2[i+1][j] - ps2[i][j-1] + ps2[i+1][j-1];
}
}
}
void s3(int N, int n, int m){
if(n-1 >= 1){
for(int i=1; i<n; ++i){
for(int j=N; 1<=j; --j){
ps3[i][j] = ps3[i-1][j] + ps3[i][j+1] - ps3[i-1][j+1] + exist[i][j];
}
}
}
if(m+1 <= N)
for(int i=n; i<=N; ++i) ps3[i][m+1] = countTreasure(1, m+1, i, N);
for(int i=n; i<=N; ++i){
for(int j=m; 1<=j; --j){
int t = countTreasure(1, j, i, N);
ps3[i][j] = t;
exist[i][j] = t - ps3[i-1][j] - ps3[i][j+1] + ps3[i-1][j+1];
}
}
}
void s4(int N, int n, int m){
for(int i=1; i<n; ++i){
for(int j=1; j<=N; ++j){
ps4[i][j] = ps4[i-1][j]+ps4[i][j-1]-ps4[i-1][j-1]+exist[i][j];
}
}
for(int i=n; i<=N; ++i){
for(int j=1; j<m; ++j){
ps4[i][j] = ps4[i-1][j]+ps4[i][j-1]-ps4[i-1][j-1]+exist[i][j];
}
}
for(int i=n; i<=N; ++i){
for(int j=m; j<=N; ++j){
int t = countTreasure(1, 1, i, j);
ps4[i][j] = t;
exist[i][j] = t - ps4[i-1][j] - ps4[i][j-1] + ps4[i-1][j-1];
}
}
}
void findTreasure (int N) {
int mid = (N)/2;
s1(N, mid, mid);
s2(N, mid, mid+1);
s3(N, mid+1, mid);
s4(N, mid+1, mid+1);
for(int i=1; i<=N; ++i){
for(int j=1; j<=N; ++j){
if(exist[i][j]){
Report(i, j);
}
}
}
}
