Little Cyan Fish has a rectangle with $n$ rows and $m$ columns, where both rows and columns are indexed starting from $0$. The cell at row $i$ and column $j$ can be denoted by $(i, j)$ ($0 \le i \le n - 1, 0 \le j \le m - 1$). Initially, all cells exist (are not deleted).

Little Cyan Fish calls two cells $(x_a, y_a)$ and $(x_b, y_b)$ adjacent if and only if $|x_a - x_b| + |y_a - y_b| = 1$. In other words, these two cells share a common boundary (also known as 4-adjacent). For two cells $p = (x_a, y_a)$ and $q = (x_b, y_b)$, if they can be connected through a sequence of adjacent undeleted cells, then cells $p$ and $q$ are said to be connected (4-connected).

For example, consider the situation above (where black cells represent deleted cells and white cells represent undeleted cells): cell A and cell B are adjacent. Cell A is connected to cell B and cell C, but cell A and cell D are not connected.

Now, Little Cyan Fish is going to perform some operations in his dream. In each operation, Little Cyan Fish chooses a cell $(x, y)$ and deletes the cell $(x, y)$.

Little Cyan Fish is very curious about how many of the remaining undeleted cells in the current rectangle are cut vertices (articulation points) after each deletion. Specifically:

• For a cell $r = (x_r, y_r)$, if there exist two cells $p = (x_p, y_p)$ and $q = (x_q, y_q)$ such that $p$ and $q$ are connected in the grid, but are no longer connected after deleting cell $r$, then $r$ is called a cut vertex.

For example, in the figure above, cell E is a cut vertex. This is because for cell A and cell C, they are connected before deleting cell E, but are no longer connected after deleting cell E.

However, because Little Cyan Fish's dream is very magical, you cannot predict his subsequent operations. Therefore, you need to answer all these operations online. Specifically, the $(x, y)$ given in the $i$-th ($2 \le i \le q$) operation depends on the result returned by the $i-1$-th operation. Please help Little Cyan Fish answer all queries under this restriction.

Input

The first line contains three integers $n$, $m$, and $q$ ($2 \le n, m \le 500$, $1 \le q \le n \cdot m$).

The next $q$ lines each contain two integers $x'_i, y'_i$ ($0 \le x'_i < n, 0 \le y'_i < m$), representing the encrypted coordinates $(x_i, y_i)$ of the deleted cell. If the answer to the previous query is $preans$, then the actual $x_i = (x'_i + preans) \bmod n$ and $y_i = (y'_i + preans) \bmod m$. Initially, we consider $preans = 0$.

It is guaranteed that the decrypted $(x_i, y_i)$ are pairwise distinct. That is, the same cell will not be deleted multiple times.

Output

For each operation, output a single line containing an integer denoting the number of cut vertices after that deletion operation.

Example

Input 1

5 5 12
0 1
0 1
1 4
2 3
4 1
2 4
1 1
4 2
2 1
4 2
1 0
0 0

Output 1

1
2
2
6
5
7
10
7
6
7
7
4

Note

The decrypted data:

5 5 12
0 1
1 2
3 1
4 0
0 2
2 4
3 3
4 2
4 3
0 3
3 2
2 2

Below is the order in which each cell is colored black.