Кола
На площині задано 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. Зазначимо, що спочатку потрібно знайти відповідь на запит, а потім задати колу нове положення. У процесі запитів радіуси кіл не змінюються. Зміна положення кіл впливає на подальші запити, тобто, кожен наступний запит виконується з урахуванням усіх попередніх переміщень.