FindingKids

In Amagi Brilliant Park there is a famous bumper car ride. The park administration emphasizes safety. When they observed other bumper car rides, they noticed that collisions of more than two cars are very dangerous. Therefore, they decided to design a unique ride where this cannot happen.

This ride consists of a single track that is very long but only one car wide. For the purpose of this problem we will visualize the ride as the real number line and cars as points on this line. The line goes from the left to the right and coordinates increase towards the right.

All cars are always in motion: at any moment, some cars are going to the left and all other cars are going to the right. All cars always move at the same constant speed of 1 unit per microsecond. Whenever two cars occupy the same point, they bump into each other and both of them immediately switch their direction (from left to right and vice versa).

A group of n kids from a certain elementary school just entered the park. Kids love bumper cars, so all n of them went on the ride at the same time. Each kid chose a different car. All n cars start in distinct locations. There are no other cars on the ride. The kids are numbered 0 through n-1 in no particular order. For each kid i, you will be given its initial position pos[i] and the initial direction dir[i] of its car. The exact format is specified below.

The teacher is worried about being too far away from the kids. She asked you q queries. The queries are numbered from 0 to q-1. Each query has two parameters: kid[i] and time[i]. Here, kid[i] is the number of one particular kid, and time[i] is the time in microseconds from the beginning of the ride.

The answer to each query should be the distance between position 0 and the position of kid[i] at time[i]. Return the sum of answers to all the queries.

You are given the ints n and q mentioned above. You are also given ints A, B, and C. These are the seeds of a pseudo-random generator that will output the values of pos, dir, kid, and time. The pseudocode of the generator follows.

let M = 1,000,000,007

for i from 0 to n-1, inclusive:
    A := (A * B + C) modulo M
    p := A modulo (M - n + i + 1)
    if p is already in pos:
        p := M - n + i
    pos[i] := p
    if p modulo 2 == 0:
        dir[i] := "right"
    else:
        dir[i] := "left"

for i from 0 to q-1, inclusive:
    A := (A * B + C) modulo M
    kid[i] := A modulo n
    A := (A * B + C) modulo M
    time[i] := A