#include <bits/stdc++.h>
using namespace std;
// ===== precyzyjne liczenie odległości (bez overflow) =====
static inline __int128 sq128(long long v){ return (__int128)v * v; }
static inline bool circles_intersect(long long x1,long long y1,long long r1,
long long x2,long long y2,long long r2){
__int128 dx = (__int128)x1 - x2;
__int128 dy = (__int128)y1 - y2;
__int128 dist2 = dx*dx + dy*dy;
__int128 sr = (__int128)r1 + r2;
return dist2 <= sr*sr;
}
struct Circle {
long long x, y, r;
int id; // 0..n-1
};
// ===== Spatial Hash (siatka) =====
struct SpatialHash {
long long S; // rozmiar boku komórki
// klucz komórki: 64-bit (łączymy (cx, cy))
struct Key {
long long cx, cy;
bool operator==(const Key& o) const { return cx==o.cx && cy==o.cy; }
};
struct KeyHash {
size_t operator()(const Key& k) const {
// mix 64-bitów
uint64_t x = std::hash<long long>()(k.cx);
uint64_t y = std::hash<long long>()(k.cy);
// splitmix64
auto mix = [](uint64_t z){
z += 0x9e3779b97f4a7c15ULL;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
};
return (size_t)(mix(x) ^ (mix(y)<<1));
}
};
// w każdej komórce trzymamy zbiór id kół
unordered_map<Key, unordered_set<int>, KeyHash> cell2ids;
// dla szybkiego kasowania: dla każdego koła lista komórek, w których siedzi
vector<vector<Key>> id_cells;
SpatialHash() : S(1) {}
// iloraz podłogi dla liczb ujemnych
static inline long long floordiv(long long a, long long b){
// b > 0
if (a >= 0) return a / b;
return - ( ( -a + b - 1 ) / b );
}
inline Key key_of_point(long long x, long long y) const {
return { floordiv(x, S), floordiv(y, S) };
}
// dodaj koło do wszystkich komórek przecinanych przez jego bbox
void add_circle(const Circle& c, int id){
long long xl = c.x - c.r, xr = c.x + c.r;
long long yl = c.y - c.r, yr = c.y + c.r;
long long cx1 = floordiv(xl, S), cx2 = floordiv(xr, S);
long long cy1 = floordiv(yl, S), cy2 = floordiv(yr, S);
vector<Key> keys;
keys.reserve((cx2-cx1+1) * (cy2-cy1+1));
for(long long cx = cx1; cx <= cx2; ++cx){
for(long long cy = cy1; cy <= cy2; ++cy){
Key k{cx, cy};
cell2ids[k].insert(id);
keys.push_back(k);
}
}
id_cells[id] = std::move(keys);
}
// usuń koło ze wszystkich wcześniej zapamiętanych komórek
void remove_circle(int id){
for(const Key& k : id_cells[id]){
auto it = cell2ids.find(k);
if(it != cell2ids.end()){
it->second.erase(id);
if(it->second.empty()) cell2ids.erase(it);
}
}
id_cells[id].clear();
}
// zwraca unikalnych kandydatów z komórek bbox zapytania
template<class FnPush>
void for_candidates_bbox(long long xl, long long yl, long long xr, long long yr, FnPush push){
long long cx1 = floordiv(xl, S), cx2 = floordiv(xr, S);
long long cy1 = floordiv(yl, S), cy2 = floordiv(yr, S);
for(long long cx = cx1; cx <= cx2; ++cx){
for(long long cy = cy1; cy <= cy2; ++cy){
Key k{cx, cy};
auto it = cell2ids.find(k);
if(it == cell2ids.end()) continue;
for(int id : it->second) push(id);
}
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<Circle> a(n);
long long minx=LLONG_MAX, maxx=LLONG_MIN, miny=LLONG_MAX, maxy=LLONG_MIN;
for(int i=0;i<n;i++){
cin >> a[i].x >> a[i].y >> a[i].r;
a[i].id = i;
minx = min(minx, a[i].x);
maxx = max(maxx, a[i].x);
miny = min(miny, a[i].y);
maxy = max(maxy, a[i].y);
}
// Porządek wyboru: malejąco po r, przy remisie rosnąco po id
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j){
if(a[i].r != a[j].r) return a[i].r > a[j].r;
return i < j;
});
// Dobór rozmiaru komórki S ~ (rozpiętość / sqrt(n)), min 1
long long spanx = maxx - minx + 1;
long long spany = maxy - miny + 1;
long double avgspan = (long double)spanx + (long double)spany;
long double rootn = max(1.0L, sqrtl((long double)max(1, n)));
long long S = (long long) max(1.0L, (avgspan / 2.0L) / rootn);
SpatialHash grid;
grid.S = S;
grid.id_cells.assign(n, {});
vector<char> alive(n, 1);
vector<int> killer(n, -1);
// wstaw wszystkie koła do siatki
for(int i=0;i<n;i++){
grid.add_circle(a[i], i);
}
// iterujemy w porządku wyboru
vector<char> seen_flag(n, 0); // do odszumienia kandydatów (unikaty)
vector<int> candidates_buf; candidates_buf.reserve(1024);
for(int idx : order){
if(!alive[idx]) continue; // już usunięte wcześniej
// to koło zostaje WYBRANE i zabija siebie i sąsiadów-kolidujących
// najpierw zbierz kandydatów z bbox
long long xl = a[idx].x - a[idx].r;
long long xr = a[idx].x + a[idx].r;
long long yl = a[idx].y - a[idx].r;
long long yr = a[idx].y + a[idx].r;
candidates_buf.clear();
grid.for_candidates_bbox(xl, yl, xr, yr, [&](int j){
if(!seen_flag[j]){
seen_flag[j] = 1;
candidates_buf.push_back(j);
}
});
// sam wybrany też ma wynik = on sam
killer[idx] = idx + 1; // 1-based w odpowiedzi
alive[idx] = 0;
grid.remove_circle(idx);
// sprawdź kandydatów i usuń kolidujących, którzy nadal żyją
for(int j : candidates_buf){
seen_flag[j] = 0; // od razu czyścimy flagę
if(j == idx) continue;
if(!alive[j]) continue;
if(circles_intersect(a[idx].x, a[idx].y, a[idx].r,
a[j].x, a[j].y, a[j].r)){
killer[j] = idx + 1;
alive[j] = 0;
grid.remove_circle(j);
}
}
}
// koła, które nigdy nie zostały „złapane” przez większe (np. samotne),
// muszą mieć killer ustawiony na siebie (zostają wybrane, gdy przyjdzie ich kolej)
for(int i=0;i<n;i++){
if(killer[i] < 0) killer[i] = i + 1;
}
for(int i=0;i<n;i++){
if(i) cout << ' ';
cout << killer[i];
}
cout << '\n';
return 0;
}
