H. Amphitheater
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In an amphitheater, there are $$$N$$$ rows. The first row has $$$K$$$ seats. Each subsequent row has $$$2$$$ more seats than the previous one, and the second and penultimate seats in each row are positioned directly behind the first and last seats of the previous row, respectively.

If a person in the audience begins to applaud, then after $$$1$$$ second, the audience members sitting in the adjacent seats (to the left, right, front, and back) will also begin to applaud, and this continues with their neighbors, and so on.

You and your acquaintances bought $$$Q$$$ tickets. Each ticket specifies the coordinates of a seat in the auditorium: the row number $$$R_i$$$ and the seat number $$$C_i$$$. For each ticket, calculate how many seconds $$$T_i$$$ after the applause starts at the seat indicated on the ticket, it will take for all the spectators in the auditorium to begin applauding, assuming that there are no empty seats.

Input

The first line contains two integers — the number of rows $$$N$$$ ($$$1 \le N \le 10^6$$$) and the number of seats in the first row $$$K$$$ ($$$1 \le K \le 10^6$$$).

The second line contains the number of tickets $$$Q$$$ ($$$1 \le Q \le 10^5$$$).

The following lines describe the tickets: $$$R_i$$$ — the row number, $$$C_i$$$ — the seat number in the row. Rows and seat numbers are numbered starting from $$$1$$$. It is guaranteed that the seat ($$$R_i$$$, $$$C_i$$$) exists in the auditorium.

Output

For each ticket, output the number $$$T_i$$$ in a separate line — how many seconds it takes for everyone in the auditorium to be clapping after applause starts at the seat $$$i$$$.

Example
Input
4 1
3
1 1
4 2
3 3
Output
6
5
4