Phalanx

Sylvia is a girl who loves learning.

Some time ago, Sylvia participated in the school's military training. As everyone knows, military training requires standing in a formation. The formation Sylvia is in has $n \times m$ students, with $n$ rows and $m$ columns.

For convenience, at the beginning of the training, the instructor assigned numbers to the students in the formation from $1$ to $n \times m$ in order from front to back and left to right (see the example below). That is, initially, the student in the $i$-th row and $j$-th column has the number $(i - 1) \times m + j$.

However, during the formation practice, students often need to leave the formation for various reasons. In one day, a total of $q$ such departure events occurred. Each departure event can be described by $(x, y)$ ($1 \le x \le n, 1 \le y \le m$), representing the student in the $x$-th row and $y$-th column leaving the formation.

After a student leaves the formation, a vacancy is created. To keep the formation tidy, the instructor will issue the following two commands in sequence:

1. Align to the left: The first column remains unchanged, and all students shift to the left to fill the vacancy. It is not difficult to see that after this command, the vacancy is at the $x$-th row and $m$-th column.
2. Align forward: The first row remains unchanged, and all students shift forward to fill the vacancy. It is not difficult to see that after this command, the vacancy is at the $n$-th row and $m$-th column.

The instructor stipulates that no two or more students can leave the formation at the same time. That is, after the previous student who left the formation returns, the next student can leave. Therefore, when a student is about to return to the formation, there is one and only one vacancy at the $n$-th row and $m$-th column, and this student will automatically fill this position.

Since standing in formation is very boring, Sylvia wants to calculate the number of the student who leaves the formation in each departure event.

Note: The number of each student does not change with the occurrence of departure events, and the numbers of students in the formation may be out of order after a departure event occurs.

Input

The first line contains three space-separated integers $n, m, q$, representing a formation of $n$ rows and $m$ columns, with a total of $q$ events.

The next $q$ lines describe the $q$ events in the order they occur. Each line contains two integers $x, y$, separated by a space, representing that the student currently in the $x$-th row and $y$-th column leaves the formation in this departure event.

Output

For each event in the order of input, output one integer per line, representing the number of the student who left the formation in that departure event.

Examples

Input 1

2 2 3
1 1
2 2
1 2

Output 1

1
1
4

Note 1

The process of the formation is shown in the figure below, where each row describes an event.

In the first event, the student with number $1$ leaves the formation, and the vacancy is at the first row and first column. Then all students shift left, the student with number $2$ moves one step to the left, and the vacancy moves to the first row and second column. Then all students shift forward, the student with number $4$ moves one step forward, and the vacancy moves to the second row and second column. Finally, the student with number $1$ returns to fill the vacancy.

Constraints

It is guaranteed that for every event, $1 \le x \le n$ and $1 \le y \le m$.

Figure 1. The process of the formation