#include <bits/stdc++.h>
using namespace std;
namespace {
const unsigned int buffer_size = 1 << 16;
char input_buffer[buffer_size + 1];
unsigned int bytes_read = 0;
unsigned int input_index = 0;
inline char next_char() {
if (input_index == bytes_read) {
bytes_read = fread(input_buffer, sizeof(char), buffer_size, stdin);
input_buffer[bytes_read] = '\0'; //sentinel
input_index = 0;
}
return input_buffer[input_index++];
}
inline int next_int() {
char c = 0;
int ans = 0;
while (c < '-')
c = next_char();
bool neg = false;
if (c == '-') {
neg = true;
c = next_char();
}
for (; c >= '0'; c = next_char())
ans = (ans << 1) + (ans << 3) + c - '0';
return neg ? -ans : ans;
}
inline void next_str(char* str) {
char c = next_char();
while (c > ' ') {
*str++ = c;
c = next_char();
}
*str = '\0';
}
char output_buffer[buffer_size];
unsigned int output_index = 0;
inline void write_flush() {
fwrite(output_buffer, sizeof(char), output_index, stdout);
output_index = 0;
}
inline void write_char(char c) {
output_buffer[output_index++] = c;
if (output_index == buffer_size)
write_flush();
}
inline void write_int(int num) {
if (num >= 10)
write_int(num / 10);
write_char(num % 10 + '0');
}
/**
* Currently this design only allows one arena per arena size
*
* @tparam SIZE size of arena in bytes, default is 200 MB
*/
template <size_t SIZE = 500 << 20> class Arena {
static char buf[];
static size_t buf_ind;
public:
template <class T> struct Allocator {
typedef T value_type;
Allocator() {}
template <class U> Allocator(const U&) {}
T* allocate(size_t n) {
buf_ind -= n * sizeof(T);
buf_ind &= 0 - alignof(T);
return (T*) (buf + buf_ind);
}
void deallocate(T*, size_t) {}
};
/**
* Frees the arena, be very sure no allocation is still used when calling this
*/
static void Clear() {
buf_ind = SIZE;
}
};
template <size_t SIZE> char Arena<SIZE>::buf[SIZE];
template <size_t SIZE> size_t Arena<SIZE>::buf_ind = SIZE;
#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()
typedef int64_t ll;
typedef double dd;
ll Sq(ll x) {
return x * x;
}
struct Circle {
int x, y, r, id;
bool operator<(const Circle& c) const {
return make_pair(-r, id) < make_pair(-c.r, c.id);
}
bool Contains(int p, int q) const {
return Sq(p - x) + Sq(q - y) <= Sq(r);
}
bool Intersects(const Circle& c) const {
return Sq(x - c.x) + Sq(y - c.y) <= Sq(r + c.r);
}
bool Contains(int x1, int y1, int x2, int y2) const {
return Contains(x1, y1) and Contains(x1, y2) and Contains(x2, y1) and Contains(x2, y2);
}
static bool In(int a, int b, int q) {
// is q in [a,b]
return a <= q and q <= b;
}
// does this circle intersect square
// check if an edge intersects
// or if circle is in square
bool Intersects(int x1, int y1, int x2, int y2) const {
return
// horizontal edge intersects
(y1 <= y + r and y - r <= y2 and (In(x - r, x + r, x1) or In(x - r, x + r, x2)))
// vertical edge intersects
or (x1 <= x + r and x - r <= x2 and (In(y - r, y + r, y1) or In(y - r, y + r, y2)))
// circle is in square
or (In(x1, x2, x) and In(y1, y2, y));
}
};
struct Node {
static Node pool[];
static int next_node;
int quad[4];
int x1, x2, y1, y2;
vector<int> ids; // sorted by largest radius first
Node() {}
Node(int x1, int y1, int x2, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {
memset(quad, 0, sizeof(quad));
}
static int Alloc(int x1, int y1, int x2, int y2) {
// return new(allocator.allocate(1)) Node(x1, x2, y1, y2);
new(pool + next_node) Node(x1, y1, x2, y2);
return next_node++;
}
void Insert(const vector<Circle>& circs) {
if (x1 + 1 == x2 or SIZE(circs) <= 500) {
// DEBUG(x1, y1, x2, y2);
// RARA(c, circs) DEBUG(c.id);
RARA(c, circs) {
ids.push_back(c.id);
// nodes[c.id].push_back(this);
}
return;
}
const int xm = (x1 + x2) / 2;
const int ym = (y1 + y2) / 2;
vector<Circle> ccs[4];
RARA(c, circs) {
if (c.Contains(x1, y1, x2, y2)) {
// DEBUG(x1, y1, x2, y2, c.id);
ids.push_back(c.id);
// nodes[c.id].push_back(this);
continue;
}
if (c.Intersects(xm, ym, x2, y2))
ccs[0].push_back(c);
if (c.Intersects(x1, ym, xm, y2))
ccs[1].push_back(c);
if (c.Intersects(x1, y1, xm, ym))
ccs[2].push_back(c);
if (c.Intersects(xm, y1, x2, ym))
ccs[3].push_back(c);
}
VEVE(i, 0, 4) if (not ccs[i].empty()) {
if (not quad[i]) {
quad[i] = Alloc(i == 1 or i == 2 ? x1 : xm,
i >= 2 ? y1 : ym,
i == 1 or i == 2 ? xm : x2,
i >= 2 ? ym : y2);
}
pool[quad[i]].Insert(ccs[i]);
}
}
void Erase(const Circle& c, const vector<Circle>& circs, vector<int>& res) {
static vector<int> temp;
// if (x1 + 1 == x2 or c.Contains(x1, y1, x2, y2)) {
// DEBUG(c.x, c.y, c.r, x1, y1, x2, y2, ids);
temp.clear();
RARA(id, ids) {
if (res[id] != -(SIZE(circs) + 1)) {
} else if (c.Intersects(circs[id])) {
res[id] = c.id;
} else {
temp.push_back(id);
}
}
ids.swap(temp);
// }
RARA(qq, quad) {
Node* q = pool + qq;
if (qq and c.Intersects(q->x1, q->y1, q->x2, q->y2)) {
q->Erase(c, circs, res);
}
}
}
};
Node Node::pool[12000000];
int Node::next_node = 1;
void Solve(ll) {
// DEBUG(sizeof(Node::pool));
int n;
n = next_int();
// cin >> n;
vector<Circle> circs(n);
vector<int> res(n, -(n + 1));
{
map<tuple<int, int, int>, int> was;
VEVE(i, 0, n) {
auto& c = circs[i];
c.x = next_int();
c.y = next_int();
c.r = next_int();
// cin >> c.x >> c.y >> c.r;
c.id = i;
int& w = was[make_tuple(c.x, c.y, c.r)];
if (w > 0) {
res[i] = -w;
} else {
w = i + 1;
}
}
}
const int PW = 1 << 30;
Node* root = Node::pool + Node::Alloc(-PW, -PW, PW, PW);
vector<int> ord(n);
iota(ALL(ord), 0);
sort(ALL(ord), [&](int a, int b) {
return circs[a] < circs[b];
});
set<int> rem_ids;
VEVE(i, 0, n) if (res[ord[i]] == -(n + 1)) rem_ids.insert(i);
VEVE(its, 0, min(n, (int) (1e7) / n)) {
if (rem_ids.empty())
break;
const auto& c = circs[ord[*rem_ids.begin()]];
for (auto it = rem_ids.begin(); it != rem_ids.end();) {
if (c.Intersects(circs[ord[*it]])) {
res[ord[*it]] = c.id;
rem_ids.erase(it++);
} else {
++it;
}
}
}
vector<Circle> rem;
rem.reserve(n);
RARA(i, rem_ids) {
rem.push_back(circs[ord[i]]);
// DEBUG(i + 1);
}
root->Insert(rem);
RARA(c, rem) if (res[c.id] == -(n + 1)) {
root->Erase(c, circs, res);
}
RARA(r, res) if (r < 0) r = res[-r - 1];
RARA(r, res) {
// cout << (r + 1) << ' ';
write_int(r + 1);
write_char(' ');
}
// cout << endl;
write_char('\n');
write_flush();
}
void Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
}
int32_t
main() {
#ifdef AZN
freopen("input.txt", "r", stdin);
#endif
Init();
ll tests = 1;
VEVE(test, 1, tests + 1) Solve(test);
return 0;
}
