#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
/*
20
00000000000000000001
00000000000000000001
00000001000000000001
00000001000000000001
00000001000001000001
00000000000000000001
00000000000000000001
00111000000000000001
00111000000000000001
00111000000000000001
00000000000000000001
00000000001100000001
00000000000000000001
00000100000000000001
00000000000000000001
00000000000111000001
00000000000000000001
11111111111111111111
00000000000000000001
00000000000000000001
*/
int n;
/**
01
23
**/
int quarter(int r, int c) { return (r > n / 2) * 2 + (c > n / 2); }
vector<pair<int, int>> neighbours(int r, int c) {
int q = quarter(r, c);
if (q == 0)
return {{r+1, c}, {r, c+1}, {r+1, c+1}};
else if (q == 1)
return {{r+1, c}, {r, c-1}, {r+1, c-1}};
else if (q == 2)
return {{r-1, c}, {r, c+1}, {r-1, c+1}};
else
return {{r-1, c}, {r, c-1}, {r-1, c-1}};
}
map<vector<int>, int> mem;
int get(int r1, int c1, int r2, int c2) {
if (mem.count({r1, c1, r2, c2}))
return mem[{r1, c1, r2, c2}];
int res = countTreasure(r1, c1, r2, c2);
mem[{r1, c1, r2, c2}] = res;
return res;
}
void findTreasure (int N) {
n = N;
int pref[4][n + 1][n + 1];
memset(pref, 0, sizeof(pref));
char marked[4][n + 1][n + 1];
memset(marked, 0, sizeof(marked));
rep(z, 0, 4)
rep(i, 1, n + 1)
rep(j, 1, n + 1)
if (quarter(i, j) == z) {
for (pair<int, int> k : neighbours(i, j))
if (quarter(k.first, k.second) != z && !marked[z][k.first][k.second]) {
if (z == 0)
pref[z][k.first][k.second] = get(k.first, k.second, n, n);
else if (z == 1)
pref[z][k.first][k.second] = get(k.first, 1, n, k.second);
else if (z == 2)
pref[z][k.first][k.second] = get(1, k.second, k.first, n);
else
pref[z][k.first][k.second] = get(1, 1, k.first, k.second);
marked[z][k.first][k.second] = 1;
}
if (quarter(i, j) == 0)
pref[z][i][j] = get(i, j, n, n);
else if (quarter(i, j) == 1)
pref[z][i][j] = get(i, 1, n, j);
else if (quarter(i, j) == 2)
pref[z][i][j] = get(1, j, i, n);
else
pref[z][i][j] = get(1, 1, i, j);
}
int ans[n + 1][n + 1];
rep(i, 1, n + 1)
rep(j, 1, n + 1) {
int z = quarter(i, j);
if (z == 0)
ans[i][j] = pref[z][i][j] - pref[z][i + 1][j] - pref[z][i][j + 1] + pref[z][i + 1][j + 1];
else if (z == 1)
ans[i][j] = pref[z][i][j] - pref[z][i + 1][j] - pref[z][i][j - 1] + pref[z][i + 1][j - 1];
else if (z == 2)
ans[i][j] = pref[z][i][j] - pref[z][i - 1][j] - pref[z][i][j + 1] + pref[z][i - 1][j + 1];
else
ans[i][j] = pref[z][i][j] - pref[z][i - 1][j] - pref[z][i][j - 1] + pref[z][i - 1][j - 1];
}
rep(i, 1, n + 1)
rep(j, 1, n + 1)
if (ans[i][j])
Report(i, j);
/*
ooxxoo
ooxxoo
xxxxxx
xxxxxx
ooxxoo
ooxxoo
ooxoo
ooxoo
xxxxx
ooxoo
ooxoo
*/
}
