Problem Statement

There is a grid with $H$ rows and $W$ columns.

The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$.

• For $1\le i < H,1 \le j \le W$, you can move between $(i,j)$ and $(i+1,j)$ in either direction in time $1$.
• For $1\le i \le H,1 \le j < W$, you can move between $(i,j)$ and $(i,j+1)$ in either direction in time $i$.

There are $N$ exits on the grid, and exit $i$ is at $(A_i,B_i)$.

Solve the following problem for each of $x=1,2,\ldots ,N$.

• You are initially at exit $x$. Find the minimum time required to move to another exit.

Constraints

• $1 \le H \le 10^9$
• $1 \le W \le 10^9$
• $2 \le H\times W$
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le H$
• $1 \le B_i \le W$
• $(A_i,B_i)\not=(A_j,B_j)$ when $i\not=j$
• All input values are integers.

Input

The input is given from standard input in the following format.

$H$ $W$ $N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

Output

Print $N$ lines. The $i$-th line should contain the answer to the problem for $x=i$.

Sample

10 10 6
1 2
2 3
3 3
10 7
8 2
3 5

2
1
1
13
7
5

1000000000 1000000000 2
1000000000 1
1000000000 1000000000

2999999997
2999999997