#include <bits/stdc++.h>
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept {
return itr != other.itr;
}
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept
: first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr u64 ceil_log2(const u64 x) {
u64 e = 0;
while (((u64)1 << e) < x) ++e;
return e;
}
template <class T> using Vec = std::vector<T>;
constexpr i64 MAX = 1000000000;
constexpr i64 square(const i64 x) { return x * x; }
void APIO18_circle_selection_main() {
usize N;
std::cin >> N;
Vec<i64> X(N), Y(N), R(N);
for (const auto i : rep(0, N)) {
std::cin >> X[i] >> Y[i] >> R[i];
X[i] += MAX;
Y[i] += MAX;
}
const auto intersect = [&](const usize i, const usize j) {
return square(X[i] - X[j]) + square(Y[i] - Y[j]) <= square(R[i] + R[j]);
};
i64 G = (i64)1 << ceil_log2(2 * MAX);
Vec<i64> unit;
unit.push_back(0);
Vec<usize> order(N);
std::iota(order.begin(), order.end(), (usize)0);
std::sort(order.begin(), order.end(),
[&](const usize i, const usize j) { return Y[i] < Y[j]; });
Vec<Vec<usize>> group;
group.push_back(order);
std::sort(order.begin(), order.end(), [&](const usize i, const usize j) {
return R[i] > R[j] or (R[i] == R[j] and i < j);
});
Vec<usize> ans(N);
std::iota(ans.begin(), ans.end(), (usize)0);
Vec<bool> done(N);
for (const auto center : order) {
if (done[center]) {
continue;
}
done[center] = true;
while (G / 2 >= R[center]) {
G /= 2;
Vec<i64> new_unit;
Vec<Vec<usize>> new_group;
for (const auto i : rep(0, unit.size())) {
const auto to_left = 2 * unit[i];
const auto itr = std::stable_partition(
group[i].begin(), group[i].end(),
[&](const usize i) { return X[i] / G == to_left; });
if (itr != group[i].begin()) {
new_unit.push_back(to_left);
new_group.emplace_back(group[i].begin(), itr);
}
if (itr != group[i].end()) {
new_unit.push_back(to_left + 1);
new_group.emplace_back(itr, group[i].end());
}
}
unit = std::move(new_unit);
group = std::move(new_group);
}
const auto X_c = X[center] / G;
const isize X_i =
std::lower_bound(unit.begin(), unit.end(), X_c) - unit.begin();
for (isize di = -2; di <= 2; ++di) {
const auto i = X_i + di;
if (i < 0 or i >= (isize)unit.size() or
std::abs(unit[i] - X_c) > 2) {
continue;
}
auto itr = std::partition_point(
group[i].begin(), group[i].end(), [&](const usize k) {
return Y[k] + 2 * R[center] < Y[center];
});
while (itr != group[i].end()) {
const auto k = *itr;
if (Y[k] - 2 * R[center] > Y[center]) {
break;
}
if (!done[k] and intersect(center, k)) {
ans[k] = center;
done[k] = true;
}
++itr;
}
}
}
for (const auto x : ans) {
std::cout << x + 1 << '\n';
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
APIO18_circle_selection_main();
return 0;
}
