На плоскости расположено $$$n$$$ различных окружностей. Известно, что любые две из них либо не пересекаются, либо касаются. Окружности могут вращаться вокруг своего центра в любом из двух возможных направлений, при этом между касающимися окружностями передаётся вращение: если окружности касаются внешним образом, то они вращаются в разных направлениях, а если внутренним — в одном. Требуется определить, сколько окружностей будет вращаться, если раскрутить $$$i$$$-ю окружность (обратите внимание, что раскрутить некоторые окружности невозможно — в этом случае ответ для соответствующей окружности равен 0).
В первой строке задано одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество окружностей.
В следующих $$$n$$$ строках заданы 3 целых числа — координаты ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) центра и радиус ($$$1 \leq r_i \leq 10^9$$$).
Выведите $$$n$$$ целых чисел через пробел — ответы для каждой из $$$n$$$ окружностей.
| Группа | Баллы | Доп. ограничения | Комментарий |
| $$$0$$$ | $$$0$$$ | — | Тесты из условия |
| $$$1$$$ | $$$10$$$ | $$$y_i = 0, r_1 = r_2 = \ldots = r_n$$$ | Каждый тест |
| $$$2$$$ | $$$20$$$ | $$$n \le 1000 $$$ | Каждый тест |
| $$$3$$$ | $$$15$$$ | $$$y_i = 0$$$ | Каждый тест |
| $$$4$$$ | $$$20$$$ | $$$r_1 = r_2 = \ldots = r_n$$$ | Каждый тест |
| $$$5$$$ | $$$35$$$ | — | Каждый тест |
40 9 30 7 59 7 19 4 2
2 2 2 2
71 3 21 0 15 0 35 3 75 7 310 3 16 0 1
0 0 0 2 2 1 1
В первом примере, если раскрутить окружность 1 или окружность 2, то будут вращаться окружности 1 и 2. Аналогично, если раскрутить окружность 3 или 4, будут вращаться окружности 3 и 4.
Во втором примере невозможно раскрутить окружности 1, 2 и 3 (выделены красным на картинке), так как невозможно задать им направления вращения так, чтобы во всех точках касания вращение передавалось, как описано в условии.
