Круги
На плоскости задано N кругов. Требуется ответить на Q запросов. i-ый запрос заключается в том, что сначала нужно для круга номер t_i найти количество других кругов, с каждым из которых он имеет хотя бы одну общую точку. Далее нужно переместить круг t_i в новое место на плоскости. Под кругом понимается окружность и все точки внутри нее.
seed_k=(31 313 131 * seed_{k-1} + 13 131 313) mod 1 000 000 007
Чтобы получить очередное значение необходимых для задачи данных, надо взять очередной элемент последовательности {seed_k}. Обозначим это действие как nextint().
Данные генерируются в таком порядке:
Где x_i и y_i - начальные координаты i-го круга, r_i - радиус i-го круга. t_j - номер интересующего круга в j-ом запросе. new_x_j и new_y_j - новые координаты центра, которые получит круг t_j после выполнения j-го запроса. Круги нумеруются начиная с 1 в порядке генерации.
Входные данные
Три целых числа: N, Q и seed_0 (1 ≤ N ≤ 1000000, 1 ≤ Q ≤ 100000, 0 ≤ seed_0 ≤ 1000000006) - количество кругов, количество запросов и нулевой элемент последовательности псевдослучайных чисел. Отметим, что генерация начинается с первого элемента, то есть, x_{1 }= seed_1 mod 1000000.
Выходные данные
Q строк. i-ая строка должна содержать одно целое число - количество кругов, с которыми на момент выполнения i-го запроса пересекается круг номер t_i. Отметим, что необходимо сначала найти ответ на запрос, а после этого задать кругу новое положение. В процессе запросов радиусы кругов не меняются. Изменение положения кругов влияет на дальнейшие запросы, то есть, каждый следующий запрос выполняется с учетом всех предыдущих перемещений.