Cho \(n\) hình tròn \(c_1, c_2, \ldots, c_n\) trên mặt phẳng Đề-các. Hãy thực hiện những việc sau:

1. Lựa chọn hình tròn \(c_i\) có bán kính lớn nhất. Nếu có nhiều lựa chọn cùng có bán kính (lớn nhất), chọn hình có chỉ số nhỏ nhất (nghĩa là \(i\) nhỏ nhất).

2. Xóa hình tròn \(c_i\) và tất cả các hình tròn giao với \(c_i\). Hai hình tròn giao nhau nếu tồn tại một điểm thuộc cả hai hình tròn. Một điểm thuộc một hình tròn nếu nó nằm trong hình tròn hoặc nó nằm trên biên của hình tròn đó.

3. Lặp lại công việc 1 và 2 cho đến khi không còn hình tròn nào.

{{asset:apio18circle/circles.png}}

Ta nói \(c_i\) bị loại bỏ bởi \(c_j\) nếu \(c_j\) là hình tròn được chọn trong lần lặp mà \(c_i\) bị xóa. Đối với mỗi hình tròn, tìm ra hình tròn loại bỏ nó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số lượng hình tròn (\(1 \le n \le 3 \cdot 10^5\)).

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_i, y_i, r_i\), là toạ độ theo trục x, tọa độ theo trục y và bán kính của hình tròn \(c_i\) (\(-10^9 \le x_i, y_i \le 10^9\), \(1 \le r_i \le 10^9\)).

Dữ liệu ra

Ghi ra \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) trên dòng đầu tiên, trong đó \(a_i\) có nghĩa là \(c_i\) bị loại bỏ bởi \(c_{a_i}\).

Phân nhóm

Ví dụ

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

7 2 7 4 5 6 7 7 4 7 6

Giải thích

Hình ảnh trong phát biểu minh họa cho ví dụ đầu tiên.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.