問題文

縦 $H$ マス、横 $W$ マスのマス目があります。

上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表記します。

• $1\le i < H,1 \le j \le W$ において、 $(i,j)$ と $(i+1,j)$ は時間 $1$ で相互に行き来可能です。
• $1\le i \le H,1 \le j < W$ において、 $(i,j)$ と $(i,j+1)$ は時間 $i$ で相互に行き来可能です。

マス目上には $N$ 個の出口があり、出口 $i$ は $(A_i,B_i)$ にあります。

$x=1,2,\ldots ,N$について次の問題を解いてください。

• 始め出口 $x$ にいます。別の出口までの移動にかかる時間のうち、最小のものを求めてください。

制約

• $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$
• $i\not=j$ のとき $(A_i,B_i)\not=(A_j,B_j)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$N$ 行出力せよ。 $i$ 行目には $x=i$ のときの問題の答えを出力せよ。

サンプル

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