#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <list>
struct Circle {
int x, y, r, idx;
Circle():
x(0), y(0), r(0), idx(0) {}
Circle(int x, int y, int r, int idx):
x(x), y(y), r(r), idx(idx) {}
bool operator == (const Circle& other) const {
if (this->x!=other.x) return 0;
if (this->y!=other.y) return 0;
if (this->r!=other.r) return 0;
if (this->idx!=other.idx) return 0;
return 1;
}
};
struct PairHasher {
std::size_t operator() (const std::pair<int,int>& p) const {
return p.first * 1000000006ULL + p.second;
}
};
int n;
std::unordered_set<int> active;
std::vector<Circle> circles;
std::vector<int> eliminator;
int idx_r[500005];
int grid_size;
std::vector<std::tuple<int,int,int>> grid;
inline int64_t euclid_dist(int x1, int y1, int x2, int y2) {
return 1LL*(x1-x2)*(x1-x2) + 1LL*(y1-y2)*(y1-y2);
}
/*
d(a,b) - a.r <= b.r
sqrt((a.x-b.x)^2 + (a.y-b.y)^2) - a.r <= b.r
sqrt((a.x-b.x)^2 + (a.y-b.y)^2) <= b.r + a.r
(a.x-b.x)^2 + (a.y-b.y)^2 <= (b.r + a.r)^2
*/
inline bool intersect(const Circle& a, const Circle& b) {
return euclid_dist(a.x,a.y,b.x,b.y) <= 1LL*(a.r+b.r)*(a.r+b.r);
}
void init_grid(int size) {
grid.clear();
grid_size = size;
for (auto i : active) {
grid.emplace_back(circles[i].x/size, circles[i].y/size, i);
}
std::sort(grid.begin(),grid.end());
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> n;
for (int i = 0, x, y, r; i < n; i++) {
active.emplace(i);
std::cin >> x >> y >> r;
circles.emplace_back(x,y,r,i);
}
std::sort(circles.begin(),circles.end(),[](const Circle& a, const Circle& b) {
if (a.r!=b.r) return a.r > b.r;
return a.idx < b.idx;
});
for (int i = 0; i < n; i++) {
idx_r[circles[i].idx] = i;
}
eliminator.assign(n, 0);
init_grid(circles[0].r);
for (const auto& c : circles) {
const auto& [x, y, r, idx] = c;
if (r <= grid_size/2) {
init_grid(r);
}
if (eliminator[idx]) {
continue;
}
eliminator[idx] = idx+1;
active.erase(idx_r[idx]);
int grid_x = x / grid_size;
int grid_y = y / grid_size;
for (int gx = grid_x-2; gx <= grid_x+2; gx++) {
for (int gy = grid_y-2; gy <= grid_y+2; gy++) {
auto le = std::lower_bound(grid.begin(),grid.end(),std::tuple<int,int,int>(gx,gy,-1));
auto ri = std::lower_bound(grid.begin(),grid.end(),std::tuple<int,int,int>(gx,gy+1,-1));
for (auto it = le; it != ri; it++) {
const auto [a, b, vidx] = *it;
if (eliminator[circles[vidx].idx]) {
continue;
}
if (intersect(circles[vidx], c)) {
eliminator[circles[vidx].idx] = idx+1;
active.erase(vidx);
}
}
}
}
}
for (int i = 0; i < n; i++) {
std::cout << eliminator[i] << " ";
}
std::cout << "\n";
}
