#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> Pt;
typedef pair<LL,LL> pii;
#define X first
#define Y second
#define F first
#define S second
inline Pt operator+(const Pt &p1,const Pt &p2)
{
return make_pair(p1.X+p2.X,p1.Y+p2.Y);
}
inline Pt operator-(const Pt &p1,const Pt &p2)
{
return make_pair(p1.X-p2.X,p1.Y-p2.Y);
}
inline LL operator*(const Pt &p1,const Pt &p2)
{
return p1.X*p2.X + p1.Y*p2.Y;
}
inline LL operator^(const Pt &p1,const Pt &p2)
{
return p1.X*p2.Y - p1.Y*p2.X;
}
int n;
const int N = 300006;
int a[N];
Pt p[N];
LL r[N];
bool vis[N];
void solve_n2()
{
for (int i=1;n>=i;i++)
{
scanf("%lld %lld %lld",&p[i].X,&p[i].Y,&r[i]);
}
for (int i=1;n>=i;i++)
{
//find the max radius
int mx_r = 0;
int mx_id = -1;
for (int j=1;n>=j;j++)
{
if (!vis[j] && r[j] > mx_r)
{
mx_r = r[j];
mx_id = j;
}
}
if (mx_id == -1) break;
for (int j=1;n>=j;j++)
{
if (vis[j]) continue;
if (( (p[j]-p[mx_id])*(p[j]-p[mx_id]) ) <= (r[mx_id] + r[j])*(r[mx_id]+r[j]) )
{
a[j] = mx_id;
vis[j] = true;
}
}
}
for (int i=1;n>=i;i++)
{
if (i!=1) printf(" ");
printf("%d",a[i]);
}
puts("");
}
set<pii> R_x,L_x,xx; //store x[i]+r,x[i]-r
void del_index(int i,int a_val)
{
a[i] = a_val;
vis[i] = true;
L_x.erase(L_x.find(make_pair(p[i].X-r[i],i)));
R_x.erase(R_x.find(make_pair(p[i].X+r[i],i)));
xx.erase(xx.find(make_pair(p[i].X,i)));
}
void solve_y0()
{
priority_queue<pii> pq;
for (int i=1;n>=i;i++)
{
pq.push(make_pair(r[i],-i));
R_x.insert(make_pair(p[i].X+r[i],i));
L_x.insert(make_pair(p[i].X-r[i],i));
xx.insert(make_pair(p[i].X,i));
}
while (!pq.empty())
{
pii pp=pq.top();
pq.pop();
int ii = -pp.S;
if (vis[ii]) continue;
//cout << "ii = " << ii << endl;
auto iter_pre=xx.lower_bound(make_pair(p[ii].X,ii));
vector<int> del_id;
//delete center in (x-r,x+r)
auto iter_end = iter_pre;
++iter_end;
while ((*iter_pre).X >= p[ii].X-r[ii])
{
pii p=(*iter_pre);
//cout << "p.S = " << p.S << endl;
del_id.push_back(p.S);
if (iter_pre == xx.begin()) break;
--iter_pre;
}
//cout << "finish first while " << endl;
while (iter_end != xx.end() && (*iter_end).X <= p[ii].X+r[ii])
{
pii p=(*iter_end);
//cout << "p.SS = " << p.S <<endl;
del_id.push_back(p.S);
++iter_end;
}
//cout << "finish second while" << endl;
for (int i:del_id)
{
//cout << "i = " << i << endl;
del_index(i,ii);
}
//cout << "finish delete" <<endl;
del_id.clear();
//now, let us search x[i]-r[i] <= x[j] + r[j] <= x[i] + r[i]
auto iter1 = R_x.lower_bound(make_pair(p[ii].X-r[ii],-1));
while (iter1 != R_x.end() && (*iter1).F <= p[ii].X+r[ii])
{
pii p=(*iter1);
del_id.push_back((p.S));
iter1++;
}
for (int i:del_id)
{
del_index(i,ii);
}
del_id.clear();
//now, let us search x[i]-r[i] <= x[j] - r[j] <= x[i] + r[i]
auto iter2 = L_x.lower_bound(make_pair(p[ii].X-r[ii],-1));
while (iter2 != L_x.end() && (*iter2).F <= p[ii].X+r[ii])
{
pii p=(*iter2);
del_id.push_back(p.S);
iter2++;
}
for (int i:del_id)
{
del_index(i,ii);
}
del_id.clear();
}
for (int i=1;n>=i;i++)
{
if (i!=1) printf(" ");
printf("%d",a[i]);
}
puts("");
}
unordered_set<int> st[N];
map<pii,int> mp;
int dx[25] = {-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[25] = {-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
bool okay_r_same(int i,int j)
{
if ( ( (p[i]-p[j])*(p[i]-p[j]) ) <= (r[i]+r[j])*(r[i]+r[j]) )
{
a[j] = i;
vis[j] = true;
return true;
}
return false;
}
void solve_r_same()
{
LL M = r[1];
int _=0;
for (int i=1;n>=i;i++)
{
pii id=make_pair(p[i].X/M,p[i].Y/M);
if (mp.find(id) == mp.end())
{
mp[id] = (++_);
}
st[ mp[id] ].insert(i);
}
for (int i=1;n>=i;i++)
{
if (vis[i]) continue;
pii id=make_pair(p[i].X/M,p[i].Y/M);
for (int k=0;25>k;k++)
{
pii h = id+make_pair(dx[k],dy[k]);
auto iter=mp.find(h);
if (iter == mp.end()) continue;
int __ = (*iter).S;
vector<int> del_id;
for (int j:st[__])
{
if (okay_r_same(i,j))
{
del_id.push_back(j);
}
}
for (int j:del_id)
{
st[__].erase(j);
}
}
}
for (int i=1;n>=i;i++)
{
if (i!=1) printf(" ");
printf("%d",a[i]);
}
puts("");
}
//unordered_set<int> alive_index;
const int G = 1024;
unordered_map<LL,LL> mp2;
inline LL to_LL(pii p)
{
return (p.F+1000000001+G)*(2000000001+G) + (p.S + 1000000001+G);
}
int lc[N],rc[N]; //linked list for alive things
void build_graph(int R)
{
mp2.clear();
int _=0;
for (int i=rc[0];i!=n+1;i=rc[i])
{
pii id = make_pair(p[i].X/R,p[i].Y/R);
if (mp2.find(to_LL(id)) == mp2.end())
{
_++;
st[_].clear();
mp2[to_LL(id)] = _;
}
st[ mp2[ to_LL(id) ] ].insert(i);
}
}
//const int G = 7122;
inline void out(int x)
{
if (x > 9)
{
out(x/10);
}
putchar(x%10 + '0');
}
double sqrt_num[102];
void build()
{
for (int i=0;102>i;i++)
{
sqrt_num[i] = sqrt(i);
}
}
void solve()
{
priority_queue<pii> pq;
rc[0] = 1;
for (int i=1;n>=i;i++)
{
pq.push(make_pair(r[i],-i));
//alive_index.insert(i);
lc[i] = i-1;
rc[i] = i+1;
}
int cnt = -1;
LL R = -1;
int now=0;
while (!pq.empty())
{
pii pp=pq.top();
pq.pop();
int ii=-pp.S;
++now;
if (vis[ii]) continue;
//if (now%1000 == 0) cout << "now = " << now << endl;
--cnt;
if (R == -1 || cnt < 0 && r[ii]*100 < R)
{
R = r[ii];
build_graph(R);
cnt = G;
}
pii id=make_pair(p[ii].X/R,p[ii].Y/R);
for (int k=0;25>k;k++)
{
int ddx = abs(dx[k])-1 , ddy = abs(dy[k])-1;
ddx = max(ddx,0);
ddy = max(ddy,0);
if (sqrt_num[ddx*ddx + ddy*ddy]*R+0.0001 > 2*r[ii]) continue;
pii h = id+make_pair(dx[k],dy[k]);
auto iter=mp2.find( to_LL(h) );
if (iter == mp2.end()) continue;
int __ = (*iter).S;
vector<int> del_id;
for (int j:st[__])
{
if (okay_r_same(ii,j))
{
del_id.push_back(j);
}
}
for (int j:del_id)
{
st[__].erase(j);
lc[ rc[j] ] = lc[j];
rc[ lc[j] ] = rc[j];
//alive_index.erase(j);
}
}
}
for (int i=1;n>=i;i++)
{
out(a[i]);
if (i == n) putchar('\n');
else putchar(' ');
//(i==n?putchar('\n'):putchar(' '));
//if (i!=1) printf(" ");
//printf("%d",a[i]);
}
//puts("");
}
//#define getchar_unlocked getchar
inline int rit()
{
int ret=0;
int f=1;
char c;
do {
c = getchar_unlocked();
if (c == '-') f = -1;
} while (c < '0' || c>'9');
do {
ret *= 10;
ret += (c-'0');
c = getchar_unlocked();
} while ('0' <= c && c <= '9');
return f*ret;
}
int main ()
{
//out(0);
//out(1234);
//out(12);
//int n;
//scanf("%d",&n);
n = rit();
if (n <= 5000)
{
solve_n2();
return 0;
}
bool y_0 = true;
bool r_same=true;
for (int i=1;n>=i;i++)
{
p[i].X = rit() + G;
p[i].Y = rit() + G;
r[i] = rit();
//scanf("%lld %lld %lld",&p[i].X,&p[i].Y,&r[i]);
y_0 &= (p[i].Y == 0);
r_same &= (r[i]==r[1]);
}
if (y_0)
{
solve_y0();
return 0;
}
if (r_same)
{
solve_r_same();
return 0;
}
solve();
}
/*
5
3 0 2
2 0 1
5 0 2
0 0 1
6 0 2
*/
/*
3
0 0 3
1 1 3
6 6 3
*/
