eolymp
bolt
Try our new interface for solving problems
Problems

Круги

Круги

Time limit 4 seconds
Memory limit 256 MiB

На плоскости задано 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 в порядке генерации.

Input data

Три целых числа: N, Q и seed_0 (1N1000000, 1Q100000, 0seed_01000000006) - количество кругов, количество запросов и нулевой элемент последовательности псевдослучайных чисел. Отметим, что генерация начинается с первого элемента, то есть, x_{1 }= seed_1 mod 1000000.

Output data

Q строк. i-ая строка должна содержать одно целое число - количество кругов, с которыми на момент выполнения i-го запроса пересекается круг номер t_i. Отметим, что необходимо сначала найти ответ на запрос, а после этого задать кругу новое положение. В процессе запросов радиусы кругов не меняются. Изменение положения кругов влияет на дальнейшие запросы, то есть, каждый следующий запрос выполняется с учетом всех предыдущих перемещений.

Examples

Input example #1
1000000 10 0
Output example #1
3
3
1
2
5
2
2
1
5
0
Author Александр Миланин
Source Летняя школа Севастополь 2013, Волна 2, День 3