Cho \(n\) hình tròn \(\left( C_{1} \right),\ \ \left( C_{2} \right),\ \ldots,\ \left( C_{i} \right),\ ...,\ (C_{n})\) trên mặt phẳng tọa độ. Chúng ta thực hiện một cách tuần tự các bước như sau:

1. Chọn hình tròn \((C_{i})\) (trong tập các hình tròn chưa bị xóa) có bán kính lớn nhất, nếu có nhiều hình tròn có cùng bán kính lớn nhất ta chọn hình tròn có chỉ số nhỏ nhất.

2. Chúng ta xóa đi hình tròn \((C_{i})\) và tất cả các hình tròn giao với hình tròn \((C_{i})\) (hai hình tròn được gọi là giao nhau nếu tồn tại ít nhất một điểm thuộc cả hai hình tròn).

3. Lặp lại bước 1 và 2 cho đến khi không còn hình tròn nào trên mặt phẳng.

Chúng ta nói rằng hình tròn \((C_{j})\) được xóa bởi hình tròn \((C_{i})\) nếu ở lần lặp hình tròn \((C_{i})\) được chọn và \((C_{j})\) giao với hình tròn \(\left( C_{i} \right),\ (C_{i})\) được gọi là xóa bởi \(\left( C_{i} \right).\)

Yêu cầu: Với mỗi hình tròn \((C_{j})\) xác định hình tròn \((C_{i})\) được chọn để xóa \(\left( C_{j} \right).\)

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq {3.10}^{5})\) là số các hình tròn trên mặt phẳng tọa độ.

• \(n\) dòng tiếp theo mỗi dòng ghi ba số nguyên \(x_{i},\ y_{i},\ r_{i}\ ( - 10^{9} \leq x_{i},\ y_{i} \leq 10^{9},\ 1 \leq r_{i} \leq 10^{9})\). Trong đó, \((x_{i},\ y_{i})\) là tâm của hình tròn và \(r_{i}\) là bán kính của hình tròn \((C_{i})\).

Kết quả:

• \(n\) số nguyên \(a_{1},\ a_{2},\ldots,\ a_{n}\), ở đó hình tròn \((C_{i})\) được xóa bởi hình tròn \(\left( C_{a_{i}} \right),\ i = 1,2,\ldots,n.\)

Ví dụ:

cc.inp	cc.out	Hình minh họa
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:

Lặp lần 1: Hình tròn số \(7\) được chọn, các hình tròn \(1,\ 3,\ 7,\ 8,\ 10\) được xóa bởi hình tròn \(7.\)

Lặp lần 2: Trên mặt phẳng còn các hình tròn số \(2,\ 4,\ 5,\ 6,\ 9,\ 11.\ \)Hình tròn số \(4\) được chọn, các hình tròn \(4,\ 9\) được xóa bởi hình tròn số \(4.\)

Lặp lần 3: Trên mặt phẳng còn các hình tròn số \(2,\ 5,\ 6,\ 11\) đều có bán kính bằng \(1,\ \)hình tròn số \(2\) được chọn vì có chỉ số nhỏ nhất. Hình tròn số \(2\) được xóa bởi hình tròn số \(2.\)

Quá trình lặp lại cho đến khi trên mặt phẳng không còn hình tròn nào nữa.

Ràng buộc:

• Ràng buộc 1: có \(10\%\) số test tương ứng với \(10\%\) số điểm của bài có \(n \leq 5000;\)

• Ràng buộc 2: có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có \(n \leq 3.\ 10^{5};y_{i} = 0;\ \forall\ i = 1,2,\ldots,n\);

• Ràng buộc 3: có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn tất cả các hình tròn có cùng bán kính;

• Ràng buộc 4: có \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.