Cola
On a plane, you are given N circles. You need to respond to Q queries. For each i-th query, you must first determine how many other circles intersect with circle number t_i. After that, circle t_i is relocated to a new position on the plane. A circle is defined as its circumference along with all the points inside it.
The sequence for generating necessary data is defined as:
seed_k = (31,313,131 * seed_{k-1} + 13,131,313) mod 1,000,000,007
To get the next required data value, use the next element from the sequence {seed_k}. This operation is referred to as nextint().
Data is generated in the following sequence:
Here, x_i and y_i are the initial coordinates of the i-th circle, and r_i is the radius of the i-th circle. t_j is the index of the circle of interest in the j-th query. new_x_j and new_y_j are the new center coordinates for circle t_j after executing the j-th query. Circles are numbered starting from 1 in the order they are generated.
Input
The input consists of three integers: N, Q, and seed_0 (1 ≤ N ≤ 1,000,000, 1 ≤ Q ≤ 100,000, 0 ≤ seed_0 ≤ 1,000,000,006) - representing the number of circles, the number of queries, and the initial element of the pseudo-random number sequence. Note that generation starts from the first element, i.e., x_{1} = seed_1 mod 1,000,000.
Output
The output should consist of Q lines. The i-th line should contain a single integer - the number of circles that intersect with circle number t_i at the time of executing the i-th query. Remember, you must first determine the answer to the query before updating the circle's position. The radii of the circles remain constant throughout the queries. The change in circle positions affects subsequent queries, meaning each query is executed considering all previous movements.