#include <iostream>
#include <set>
#include <math.h>
#include <algorithm>
#include <functional>
#include <iterator>
long double abss(long double x)
{
if (x < 0)
return -x;
else
return x;
}
long double sqr(long double x)
{
return x * x;
}
struct compare {
bool operator() (const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const {
if (lhs.first != rhs.first)
return lhs.first > rhs.first;
else
return lhs.second < rhs.second;
}
};
struct circle
{
int x, y, r;
};
circle circles[300010];
void firstSubtask(int n)
{
std::set< std::pair<int, int>, compare > set;
int visited[300010] = { 0 };
int x[300010], y[300010], r[300010];
for (int i = 1; i <= n; ++i)
{
std::cin >> x[i] >> y[i] >> r[i];
set.insert(std::make_pair(r[i], i));
}
while (set.empty() == false)
{
std::pair<int, int> p = *set.begin();
set.erase(set.begin());
int xs = x[p.second], ys = y[p.second], rs = r[p.second];
visited[p.second] = p.second;
for (auto it = set.begin(); it != set.end();)
{
std::pair<int, int> sec = *it;
int xq = x[sec.second], yq = y[sec.second], rq = r[sec.second];
long double dist = sqrt(sqr(xq * 1.0 - xs * 1.0) + sqr(yq * 1.0 - ys * 1.0));
// std::cout << p.second << " " << sec.second << " " << dist << " " << rq * 1.0 + rs * 1.0 << "\n";
if (dist <= rq * 1.0 + rs * 1.0)
{
visited[sec.second] = p.second;
it = set.erase(it);
}
else
{
++it;
}
}
}
for (int i = 1; i <= n; ++i)
{
std::cout << visited[i] << " ";
}
}
void secondSubtask(int n)
{
std::set< std::pair<int, int>, compare > radiuses;
std::set< std::pair<int, int> > right, left;
for (int i = 1; i <= n; ++i)
{
radiuses.insert(std::make_pair(circles[i].r, i));
right.insert(std::make_pair(circles[i].x + circles[i].r, i));
left.insert(std::make_pair(circles[i].x - circles[i].r, i));
}
int visited[300010] = { 0 };
while (radiuses.empty() == false)
{
auto radius = radiuses.begin();
std::pair<int, int> boss = *radius;
radiuses.erase(radius);
visited[boss.second] = boss.second;
auto it = right.find(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
int leftCheck = circles[boss.second].x - circles[boss.second].r;
int rightCheck = circles[boss.second].x + circles[boss.second].r;
while (it != right.begin())
{
--it;
std::pair<int, int> under = *it;
// std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << leftCheck << "\n";
if (under.first >= leftCheck)
{
it = right.erase(it);
left.erase(std::make_pair(circles[under.second].x - circles[under.second].r, under.second));
visited[under.second] = boss.second;
radiuses.erase(std::make_pair(circles[under.second].r, under.second));
}
else
break;
}
right.erase(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
it = left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second));
++it;
while (it != left.end())
{
std::pair<int, int> under = *it;
// std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << rightCheck << "\n";
if (under.first <= rightCheck)
{
it = left.erase(it);
right.erase(std::make_pair(circles[under.second].x + circles[under.second].r, under.second));
visited[under.second] = boss.second;
radiuses.erase(std::make_pair(circles[under.second].r, under.second));
}
else
break;
}
left.erase(left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second)));
}
for (int i = 1; i <= n; ++i)
{
std::cout << visited[i] << " ";
}
}
int main()
{
int n;
std::cin >> n;
if (n <= 5000)
{
firstSubtask(n);
return 0;
}
bool flag = true;
for (int i = 1; i <= n; ++i)
{
std::cin >> circles[i].x >> circles[i].y >> circles[i].r;
if (circles[i].y != 0)
{
flag = false;
}
}
if (flag)
{
secondSubtask(n);
return 0;
}
}
