Dan has many monkeys, and today he is training them to follow his commands. Dan draws an ~N \times M~ grid on the ground with ~N~ rows and ~M~ columns. Each cell has one monkey. Initially, the monkey at cell ~(i, j)~ has the ID of ~(i-1) \times M + j~, i.e., the 1st monkey is at cell ~(1, 1)~, the 2nd monkey is at cell ~(1, 2)~, and so on.

Dan will give ~Q~ commands. In each command, Dan will instruct the monkeys to take the following steps:

1. Dan will call the monkey at the cell ~(r, c)~ to get out of the matrix.
2. Dan will let all monkeys shift to the left if the left spot is empty.
3. Dan will let all monkeys move forward if the forward spot is empty.
4. After the above operations, the empty spot will be at ~(N, M)~. Dan will let the monkey who is out of the matrix get back and stand at the cell ~(N, M)~.

Dan wants to get a list of the monkeys' IDs who have been called to get out of the matrix, but he forgot to record this information. Can you write a program to help him?

Input Specification

The first line of input contains three integers ~N~, ~M~, and ~Q~ (~1 \le N, M, Q \le 3 \times 10^5~), indicating the number of rows, the number of columns, and the number of commands, respectively.

Each of the following ~Q~ lines contains two integers ~r_i~ and ~c_i~ (~1 \le r_i \le N~, ~1 \le c_i \le M~), indicating that the monkey at cell ~(r_i, c_i)~ is asked to get out of the matrix.

Output Specification

Output ~Q~ lines. Each line contains one integer, the ID of the monkey who has been asked to get out of the matrix

Constraints

Subtask	Points	Additional constraints
~1~	~30~	~N, M \le 1000~, ~Q \le 500~.
~2~	~20~	~N, M \le 50\,000~, ~Q \le 500~.
~3~	~20~	~N = 1~.
~4~	~30~	No additional constraints.

Sample Input

2 2 3
1 1
2 2
1 2

Sample Output

1
1
4

Explanation

The sample case is explained by the following picture.