#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
struct Circle{
ll x, y, r;
int ind;
};
bool operator<(Circle c1, Circle c2) {
return c1.ind < c2.ind;
}
ll Dist(Circle c1, Circle c2) {
return (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y);
}
bool inters(Circle c1, Circle c2) {
return Dist(c1, c2) <= (c1.r + c2.r) * (c1.r + c2.r);
}
int main() {
int n;
cin >> n;
vector<Circle> circles(n);
set<pii> ranges;
vector<pair<pii, int>> sweep;
bool subtask2 = true;
bool subtask4 = true;
map<pii, set<Circle>> grid;
ll r = 0;
for (int i = 0; i < n; i++) {
cin >> circles[i].x >> circles[i].y >> circles[i].r;
circles[i].ind = i + 1;
if (r && r != circles[i].r) {
subtask4 = false;
}
r = circles[i].r;
grid[{circles[i].x / r, circles[i].y / r}].insert(circles[i]);
if (circles[i].y) subtask2 = false;
sweep.push_back({{circles[i].x, circles[i].y - circles[i].r}, i});
sweep.push_back({{circles[i].x, circles[i].y + circles[i].r}, i});
ranges.insert({circles[i].x - circles[i].r, i + 1});
ranges.insert({circles[i].x + circles[i].r, i + 1});
}
sort(all(circles), [] (Circle c1, Circle c2) {
if (c1.r == c2.r) return c1.ind < c2.ind;
return c1.r > c2.r;
});
vi ans(n + 1);
if (subtask4) {
for (auto c : circles) {
if (ans[c.ind]) continue;
int x = c.x / r - 2;
int y = c.y / r - 2;
for (int i = x; i < x + 5; i++) {
for (int j = y; j < y + 5; j++) {
auto it1 = grid.find({i, j});
if (it1 == grid.end()) continue;
for (auto it = it1->y.begin(); it != it1->y.end();) {
if (inters(c, *it)) {
ans[it->ind] = c.ind;
it = it1->y.erase(it);
} else {
it++;
}
}
}
}
}
}
if (n <= 5000) {
sort(all(circles), [] (Circle c1, Circle c2) {
if (c1.r == c2.r) return c1.ind < c2.ind;
return c1.r > c2.r;
});
for (int i = 0; i < n; i++) {
Circle c = circles[i];
if (ans[c.ind]) continue;
ans[c.ind] = c.ind;
for (int j = i + 1; j < n; j++) {
if (!ans[circles[j].ind] && inters(circles[j], c)) {
ans[circles[j].ind] = c.ind;
}
}
}
for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
return 0;
}
if (subtask2) {
sort(all(circles), [] (Circle c1, Circle c2) {
if (c1.r == c2.r) return c1.ind < c2.ind;
return c1.r > c2.r;
});
for (auto c : circles) {
if (ans[c.ind]) continue;
ans[c.ind] = c.ind;
for (auto it = ranges.lower_bound({c.x - c.r, 0}); it != ranges.end() && it->x <= c.x + c.r; it = ranges.erase(it)) {
if (!ans[it->y]) {
ans[it->y] = c.ind;
}
}
}
for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
return 0;
}
sort(all(sweep), [&] (pair<pii, int> p1, pair<pii, int> p2) {
if (p1.x.y == p2.x.y) {
bool a, b;
a = p1.x.y < circles[p1.y].y;
b = p2.x.y < circles[p2.y].y;
return a > b;
}
return p1.x.y < p2.x.y;
});
set<pii> inside;
for (auto p : sweep) {
if (ans[p.y + 1]) continue;
auto it = inside.insert({p.x.x, p.y});
auto before = it.x, after = it.x;
if (before != inside.begin()) {
before--;
if (inters(circles[before->y], circles[p.y])) {
if (circles[before->y].r > circles[p.y].r || (circles[before->y].r == circles[p.y].r && before->y < p.y)) {
ans[before->y + 1] = ans[p.y + 1] = before->y + 1;
} else {
ans[before->y + 1] = ans[p.y + 1] = p.y + 1;
}
inside.erase(it.x), inside.erase(before);
continue;
}
}
after++;
if (after != inside.end()) {
if (inters(circles[after->y], circles[p.y])) {
if (circles[after->y].r > circles[p.y].r || (circles[after->y].r == circles[p.y].r && after->y < p.y)) {
ans[after->y + 1] = ans[p.y + 1] = after->y + 1;
} else {
ans[after->y + 1] = ans[p.y + 1] = p.y + 1;
}
inside.erase(it.x), inside.erase(after);
continue;
}
}
if (!it.y) {
inside.erase(it.x);
}
}
for (int i = 1; i <= n; i++) cout << (ans[i] ? ans[i] : i) << " ";
}
