// Remark: when the program exceeds the time limit by a small factor, I usually look for constant speedups first.
// That's a bad habit.
// (okay, bitset is a special case.)
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
auto const callRange=[](auto& object, int first, int last, auto function){
auto iterator=object.lower_bound(first);
while(iterator!=object.end() and iterator->first<last){
function(iterator->second);
++iterator;
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
using Index=int; // for circles
struct Circle{
int x, y, r;
bool intersect(Circle other) const{
assert(r>0); assert(other.r>0);
return int64_t(x-other.x)*(x-other.x)+int64_t(y-other.y)*(y-other.y)<=
int64_t(r+other.r)*(r+other.r);
}
};
int number; std::cin>>number;
std::vector<Circle> circles(number);
for(auto& [x, y, r]: circles){
std::cin>>x>>y>>r; // r==0: deleted
x+=1000000000; y+=1000000000;
assert(x>=0 and y>=0);
}
struct A{
Index index; int r;
bool operator<(A other) const{
return r!=other.r ? r<other.r: index>other.index;
}
};
std::priority_queue<A> q;
for(Index index=0; index<number; ++index)
q.push({index, circles[index].r});
std::vector<int> result(number);
assert((result.assign(number, -1), true));
struct Cell{
std::vector<Index> indices;
std::array<std::array<Cell*, 3>, 3> adjacent; // the numbering scheme is obvious. Note that [1][1] is always *this.
std::array<std::array<Cell*, 2>, 2> children;
};
std::deque<Cell> grid;
grid.resize(1);
for(Index index=0; index<number; ++index)
grid[0].indices.push_back(index);
grid[0].adjacent[1][1]=&grid[0];
std::vector<Cell*> contain(number, &grid[0]);
for(int step=30; step>1;--step){
auto oldGrid=std::move(grid);
grid.clear();
// construct all cells and children link of old layer & new contain array
for(auto& cell: oldGrid){
std::array<std::array<Cell, 2>, 2> children{};
for(Index index: cell.indices){
auto const [x, y, r]=circles[index];
assert(r>0);
children[x>>step&1][y>>step&1].indices.push_back(index);
}
for(int c=0; c<2; ++c)
for(int d=0; d<2; ++d)
if(not children[c][d].indices.empty()){
grid.push_back(std::move(children[c][d]));
auto const cur=&grid.back();
cell.children[c][d]=cur;
for(Index index: cur->indices) contain[index]=cur;
}
}
// construct adjacent link of new layer
for(auto& cell: oldGrid){
std::array<std::array<Cell*, 4>, 4> data{};
for(int c=0; c<3; ++c)
for(int d=0; d<3; ++d){
Cell* cur=(c==1 and d==1 ? &cell: cell.adjacent[c][d]);
if(not cur) continue;
for(int e=0; e<2; ++e)
for(int f=0; f<2; ++f){
unsigned const g=c*2+e-1, h=d*2+f-1;
if(g<4 and h<4) data[g][h]=cur->children[e][f];
}
}
for(int e=0; e<2; ++e)
for(int f=0; f<2; ++f){
Cell* cur=cell.children[e][f];
if(not cur) continue;
for(int c=0; c<3; ++c)
for(int d=0; d<3; ++d){
cur->adjacent[c][d]=data[c+e][d+f];
}
}
}
while(true){
if(q.empty())
goto break_outer;
auto [index, r_]=q.top();
auto const cur=circles[index]; auto const [x, y, r]=cur;
if(r==0) {
q.pop();
continue;
}
assert(r==r_);
if(r<((1<<step)>>2))
break; // goto next step -- without popping from q
q.pop();
circles[index].r=0;
assert(result[index]==-1); result[index]=index;
auto const curCell=contain[index];
assert(std::any_of(begin(grid), end(grid), [&](auto const& it){ return &it==curCell; }));
assert(curCell->adjacent[1][1]==curCell);
auto const process=[&](Cell* cell){
if(not cell) return;
cell->indices.erase(std::remove_if(begin(cell->indices), end(cell->indices), [&](Index index1){
if(index1==index){
return true;
}
auto& cur1=circles[index1];
assert(cur1.r>0);
if(cur1.intersect(cur)){
assert(result[index1]==-1);
result[index1]=index;
cur1.r=0;
return true;
} else return false;
}),cell->indices.end());
};
for(int c=0; c<3; ++c)
for(int d=0; d<3; ++d)
process(curCell->adjacent[c][d]);
}
}
break_outer:
for(Index index=0; index<number; ++index){
auto const [x, y, r]=circles[index];
assert(result[index]!=-1);
assert(r==0);
}
for(auto it: result) std::cout<<it+1<<' ';
std::cout<<'\n';
}
