// 13.12
#include "treasure.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 111
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
int arr[maxn][maxn];
void fill_arr(int r1, int c1, int r2, int c2, int val){
for(int i = r1; i <= r2; i++){
for(int j = c1; j <= c2; j++)
arr[i][j] = val;
}
}
int get(int r1, int c1, int r2, int c2){
int ret = 0;
for(int i = r1; i <= r2; i++){
for(int j = c1; j <= c2; j++)
ret += arr[i][j];
}
return ret;
}
int calc(int r1, int c1, int r2, int c2){
if(r1 > r2 || c1 > c2)
return -1;
int ret = countTreasure(1, 1, r2, c2);
ret -= get(1, 1, r2, c1 - 1);
ret -= get(1, 1, r1 - 1, c2);
ret += get(1, 1, r1 - 1, c1 - 1);
return ret;
}
void solve(int r1, int c1, int r2, int c2, int val){
// cout << r1 << " " << c1 << " " << r2 << " " << c2 << ": " << val << endl;
if(r1 > r2 || c1 > c2)
return;
if(val == 0){
fill_arr(r1, c1, r2, c2, 0);
return;
}
if(val == (r2 - r1 + 1) * (c2 - c1 + 1)){
fill_arr(r1, c1, r2, c2, 1);
return;
}
int midr = (r1 + r2) / 2;
int midc = (c1 + c2) / 2;
int area1 = calc(r1, c1, midr, midc);
solve(r1, c1, midr, midc, area1);
int area2 = calc(r1, midc + 1, midr, c2);
solve(r1, midc + 1, midr, c2, area2);
int area3 = calc(midr + 1, c1, r2, midc);
solve(midr + 1, c1, r2, midc, area3);
int area4 = calc(midr + 1, midc + 1, r2, c2);
solve(midr + 1, midc + 1, r2, c2, area4);
}
void findTreasure(int n){
memset(arr, -1, sizeof(arr));
int all = countTreasure(1, 1, n, n);
solve(1, 1, n, n, all);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(arr[i][j] == 1) {
// cout << i << " " << j << endl;
Report(i, j);
}
}
}
}
