#include "treasure.h"
#include <bits/stdc++.h>
#define LSOne(S) (S & (-S))
using namespace std;
const int MAXN = 110;
static int matriz[MAXN][MAXN],bit[MAXN][MAXN],N;
static void update(int x,int y,int delta){
for(int i = x;i<=N;i += LSOne(i)){
for(int j = y;j<=N;j += LSOne(j)){
bit[i][j] += delta;
}
}
}
static int read(int x,int y){
int ans = 0;
for(int i = x;i>0;i -= LSOne(i)){
for(int j = y;j > 0;j -= LSOne(j)){
ans += bit[i][j];
}
}
return ans;
}
static int query2d(int x1,int y1,int x2,int y2){
if(x1 > x2 || y1 > y2) return 0;
return read(x2,y2) - read(x1-1,y2) - read(x2,y1-1) + read(x1-1,y1-1);
}
void solve(int x,int left,int right,int cnt){
if(cnt == 0) return;
if(right - left + 1 == cnt){
for(int i = left;i<=right;i++){
matriz[x][i] = 1;
update(x,i,1);
}
return;
}
int mid = (left+right)/2;
int qt = countTreasure(1,1,x,mid) - query2d(1,1,x,left - 1) - query2d(1,left,x-1,mid);
solve(x,left,mid,qt);
solve(x,mid+1,right,cnt - qt);
}
void findTreasure(int n){
N = n;
memset(matriz,0,sizeof(matriz));
int cnt = countTreasure(1, 1, N, N);
int last = 0;
for(int i = 1;i<=N;i++){
int novo = countTreasure(1,1,i,N);
solve(i,1,N,novo - last);
last = novo;
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
if(matriz[i][j]) Report(i,j);
}
}
}
