#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <int, int> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n; bool s2 = 1;
pi A[MAXN], C[MAXN];
bool done[MAXN];
int ans[MAXN];
#define sq(x) ((x)*(x))
ld sqr(ll x) { return (x ? sqrtl(x) : 0); }
ld mdist(ll a, ll b, ll c, ll d) { return sqr( sq(llabs(a-c)) + sq(llabs(b-d)) ); }
vector<pi>in;
bool s4 = 1; int R = -1;
#define sdb __attribute((optimize("-Ofast"), target("arch=sandybridge")))
ll magic = 5; // odd number pls
inline bool sdb inter(int i, int j) {
if(done[j]) return 1;
if(mdist(C[i].f, C[i].s, C[j].f, C[j].s) <= (ld)A[i].f + (ld) A[j].f) {
// assert(i < j);
done[j] = 1;
ans[j] = i;
return 1;
}
else return 0;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map <int, int, custom_hash> mp;
vector <int> d;
vector<pi>ind[MAXN],tmp[MAXN];
int latest = 0;
void sdb split() {
FOR(i,0,latest+1) tmp[i].clear();
ll new_R = R/2; // if(new_R%2)new_R++;
ll co = 1;
mp.clear();
FOR(i,1,latest+1) {
if(ind[i].empty()) { assert(0); continue; } assert(co < MAXN);
if(ind[i].size()==1) { if(mp[C[ind[i][0].s].f/new_R] == 0) mp[C[ind[i][0].s].f/new_R] = co++; tmp[mp[C[ind[i][0].s].f/new_R]].pb(ind[i][0]); }
else {
ll one = LLINF;
ll two = 0;
for(auto j : ind[i]) two = max(two, C[j.s].f/new_R);
for(auto j : ind[i]) one = min(one, C[j.s].f/new_R);
ll three = -LLINF;
for(auto j : ind[i]) three = ((C[j.s].f/new_R) != one && (C[j.s].f/new_R) != two) ? C[j.s].f/new_R : three;
// if(three != -LLINF) {
// for(auto j : ind[i]) {
// cer
// ll cmp = C[j.s].f/new_R;
// if(one == cmp || two == cmp || three == cmp);
// else {
// cout << "BRUHHH\n";
// exit(0);
// }
// }
// }
// cerr << "1,2,3: " << one << ' ' << two << ' ' << three << '\n';
if(one == two) { // 1
assert(three==-LLINF);
if(mp[one]==0)mp[one] = co ++;
} else if(three == -LLINF) { // 2
if(mp[one]==0)mp[one] = co ++;
if(mp[two]==0)mp[two] = co++;
} else { // 3
swap(two,three);
if(mp[one]==0)mp[one] = co ++;
if(mp[two]==0)mp[two] = co ++;
if(mp[three]==0)mp[three] = co ++;
}
assert(co+3 < MAXN);
for(auto j : ind[i]) {
// cerr << C[j.s].f << ' ' << new_R << ' ' << C[j.s].f/new_R << ' ' << C[j.s].f/R << '\n';
tmp[mp[C[j.s].f/new_R]].pb(j);
}
// cerr << '\n' << '\n';
}
}
R=new_R; latest = co-1;
assert(co < MAXN);
FOR(i,0,latest+1) ind[i]=tmp[i];
// ll p = -LLINF;
// FOR(i,1,latest+1) {
// assert(ind[i].size());
// ll hmm = C[ind[i][0].s].f/R;
// for(auto j : ind[i]) if(hmm != C[j.s].f/R) assert(0);
// assert(hmm >= p);
// p = hmm;
// }
}
void sdb st4() {
FOR(i,0,n) {
d.pb(C[i].f/R);
}
sort(all(d)); d.resize(unique(all(d))-d.begin());
ll co = 1; for(auto i : d) mp[i] = co++;
FOR(i,0,n) {
ind[mp[C[i].f/R]].pb(pi(C[i].s,i));
latest = max(latest, mp[C[i].f/R]);
}
// FOR(i,1,latest+1) sort(all(ind[i]));
int p[n+5];
for(ll i=0;i<n;i++) p[i]=i;
sort(p,p+n,[](ll x, ll y){if(A[x].f==A[y].f)return A[x].s<A[y].s; else return A[x].f>A[y].f;});
// assert(ind[0].empty());
FOR(iii,0,n) {
ll i = p[iii]; // cerr << i+1 << ' ';
if(done[i]) continue;
done[i] = 1;
ans[i] = i; if(A[i].f < R/2) { split(); }
ll x = mp[C[i].f/R], y = C[i].s;
ll ii = i;
FOR(i,x-magic/2,x+magic/2+1) {
if(i <= 0||i>latest)continue;
// ll d = llabs(x-i) * R + R;
// auto lower = ind[i].lower_bound(pi(sqr((4ll*sq(R))-sq(d))-y, 0));
// auto upper = (ind[i].upper_bound(pi(sqr((4ll*sq(R))-sq(d))+y, LLINF)));
// if(upper != ind[i].end() && pi(lower->f,lower->s) > pi(upper->f,upper->s)) continue;
// if(lower == ind[i].end()) continue;
for(auto j = ind[i].begin(); j != ind[i].end();j++) {
if(inter(ii,j->s)) {}
}
}
}
FOR(i,0,n) assert(done[i]);
FOR(i,0,n) cout << ans[i] + 1 << ' ';
}
/* for when u need negative numbers too */
inline int sdb ri() {
bool neg = false;
int res = 0;
char c = getchar_unlocked();
while (true) {
if (c=='-') break;
if ('0'<=c && c<='9') break;
c = getchar_unlocked();
}
if (c=='-') neg = true;
else res = c-'0';
while (true) {
c = getchar_unlocked();
if (c<'0' || c>'9') break;
res = (res<<1) + (res<<3) + (c-'0');
}
if (neg) return -res;
return res;
}
void st3() {
vector<ll>inter(n,0); vector<bool>re(n,0); set <pi> ms;
vector <pi> events;
FOR(i,0,n) events.pb(pi(C[i].s-A[i].f,i)), events.pb(pi(C[i].s+A[i].f,-i-1));
sort(all(events), [] (pi x, pi y) { if(x.f != y.f) return x.f < y.f; else return x.s > y.s; } );
for(auto j : events) {
ll i = j.s;
if(i>=0) { ll r = A[i].f; ll x = C[i].f;
bool in = 1; pi near = pi(LLINF, LLINF);
if(!ms.empty()) {
// pi near = LLINF;
auto itr = ms.lower_bound(pi(x,0));
if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
assert(near.f != LLINF);
if(near.f-EPS <= (ld)r) in = 0;
}
if(in) {
ms.ins(pi(x,i)); re[i] = 1;
} else {
re[i] = 0; assert(re[near.s]);
assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
// assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
ms.erase(ms.find(pi(C[near.s].f, near.s)));
// ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
re[near.s] = 0;
inter[i] = near.s;
inter[near.s] = i;
}
} else {
i = -i-1; if(re[i] == 0) continue;
ll r = A[i].f; ll x = C[i].f;
ms.erase(ms.find(pi(x,i)));
// bool in = 1; pi near = pi(LLINF, LLINF);
// if(!ms.empty()) {
// // pi near = LLINF;
// auto itr = ms.lower_bound(pi(x,0));
// if(itr != ms.end()) near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s));
// if(itr != ms.begin()) { --itr; near = min(near, pi(mdist(C[itr->s].f,C[itr->s].s, C[i].f, C[i].s)-(ld)A[itr->s].f, itr->s)); }
// assert(near.f != LLINF);
// if(near.f-EPS <= (ld)r) in = 0;
// }
// if(!in) {
// re[i] = 0; assert(re[near.s]);
// assert((ms.find(pi(C[near.s].f, near.s))!=ms.end()));
// // assert(ms.find(pi(C[near.s].f+A[near.s].f, near.s))!=ms.end());
// ms.erase(ms.find(pi(C[near.s].f, near.s)));
// // ms.erase(ms.find(pi(C[near.s].f+A[near.s].f, near.s)));
// re[near.s] = 0;
// inter[i] = near.s;
// inter[near.s] = i;
// }
auto itr = ms.lower_bound(pi(x,0));
if(itr != ms.end()) assert(itr->f > x);
if(itr != ms.begin() && itr != ms.end()) {
ll a = prev(itr)->s, b = itr->s;
if(mdist(C[a].f,C[a].s,C[b].f,C[b].s) <= (ld)A[a].f + (ld)A[b].f){
re[a] = re[b] = 0;
inter[a] = b;
inter[b] = a;
itr=ms.erase(prev(itr));
ms.erase(itr);
}
}
}
}
FOR(i,0,n) ans[i] = i;
FOR(i,0,n) if(!re[i]&&(A[inter[i]].f>A[i].f||(A[inter[i]].f==A[i].f&&inter[i]<i))) { ans[i] = inter[i]; }
FOR(i,0,n) cout << ans[i]+1 << ' '; cout<<'\n';
}
int sdb main()
{
// freopen("int","r",stdin); // freopen("out","w",stdout);
FAST
//cin >> n;
n=ri();
FOR(i,0,n) {
C[i].f=ri();C[i].s=ri();A[i].f=ri();// cin >> C[i].f >> C[i].s >> A[i].f; if(0)in.pb(pi(C[i].f,A[i].f));
C[i].f+=1e9;
if(C[i].s) s2 = 0;
A[i].s = i;
if(R == -1) R = A[i].f;
if(R != A[i].f) s4 = 0;
R=max(R,A[i].f);
} // if(R%2)R++;
// if(st1() != st2()) {
// cerr << n << '\n';
// for(auto i : in) cerr << i.f << ' ' << i.s << '\n';
// assert(0);
// }
// assert(st1() == st2());
if(s4||n<=2e5||s2)st4();
else st3();
}
// 1 10 1 4 5 6 7 8 4 10 6
// 1 2 1 4 5 6 7 8 4 2 6
/*
3
5 0 3
10 0 2
20 0 8
4
1 0 3
10 0 5
15 0 1
20 0 10
8
1 4
14 12
6 10
0 6
14 0
9 6
3 2
0 0
*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/
