405136: GYM101804 I Infantrymen's Math

In $$$2048$$$, IME still is a military institute, but since the students started to look down on the instructors because of their questionable math knowledge, lots of Math classes are given to the instructors to make they able to command the students.

The students’ duty schedule remains the same as it’s always been. At night, some students are given some kind of job to make sure the others have a good night of sleep. There is a student designated to write this schedule, responsible of making a fair division between students so they won’t be overworking. In $$$2048$$$, this student is Xavi, a really nice, sweet, athletical, smart, good-looking guy.

Colonel Hector, commander of IME students in $$$2048$$$, is trying to innovate the students’ duty schedule. Since every student has a different ID number from $$$0$$$ to $$$n-1$$$ (being $$$n$$$ the number of students), he gave Xavi a number $$$k$$$, and Xavi has to schedule the duties calling the students by their ID in a sequence $$$s$$$ such that:

$$$$$$s_0 = 0$$$$$$ $$$$$$s_i = (s_{i-1} + k)\, \% \, n$$$$$$

($$$\%$$$ is the modulo operator).

For example, if $$$n = 7$$$ and $$$k = 2$$$, the order of students on duty is the following sequence: $$$0, 2, 4, 6, 1, 3, 5, \dots$$$

Although Colonel Hector just wants to apply some math stuff he learned, Xavi realized a problem: It could happen that some students are never called to work, and some others are called lots of times! Lucky as Xavi is, he realized the number of students is prime. Because of that, he discarded this possibility, but Colonel isn't sure about how fair is this distribution and decided to use another (a really bad and unfair one!) method to schedule the work. Xavi tried to convince Colonel to maintain this scheduling method, but the explanation got very messy and Colonel Hector didn’t believe Xavi. He decided to show the distribution of work in a program to the Colonel.

You are the guy who will help Xavi (seems that you are stuck on IME forever...). He will tell you some queries, each having the number of students called to duty and the ID of one of the students, and you have to say how many times the student with ID given will be scheduled.

The first line of input gives three integers $$$n$$$, $$$k$$$, $$$q$$$ ($$$2 \leq n, k \leq 10^9$$$, $$$1 \leq q \leq 10^5$$$) — the amount of students (IME has grown a lot!), the value of $$$k$$$ that Colonel Hector gave and the number of queries. It is guaranteed that $$$n$$$ is prime.

Then, $$$q$$$ lines follow, each containing two integer $$$c_i$$$, $$$d_i$$$ ($$$1 \leq c_i \leq 10^9$$$, $$$0 \leq d_i < n$$$) — the number of students called to duty and the ID of the student.

For each query output how many times the student with ID $$$d_i$$$ has been called, after $$$c_i$$$ calls for service.

7 1 3
1 0
12 4
14 0

1
2
2

13 3 7
3 2
4 1
12 0
12 5
50 4
200 6
9 7

0
0
1
1
4
16
0