問題文

$H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とします。

tkms 君は、グリッドの $(1,1)$ から $(H,W)$ までなるべく早く移動したいです。

グリッド上には $N$ 個のワープがあり、$i(1 \leq i \leq N)$ 個目のワープは $(a_i,b_i)$ から $(c_i,d_i)$ につながっています。逆走はできません。

tkms 君は $1$ 回の動作で

• 四方に $1$ マス移動する。つまり、$(x,y)$ にいるとき $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ のいずれか $1$ つに移動する。
• ワープを通る。

のいずれかが可能です。ワープの始点にいるとき、ワープを通らずに四方に移動しても構いません。

グリッドの外側に移動することはできません。

$(1,1)$ を出発して $(H,W)$ に到達するまでの動作の回数の最小値を求めてください。

入力

$H\ W\ N$
$a_1\ b_1\ c_1\ d_1$
$a_2\ b_2\ c_2\ d_2$
$⋮$
$a_N\ b_N\ c_N\ d_N$

• 入力はすべて整数
• $2 \leq H,W \leq 10^9$
• $0 \leq N \leq \mathbb{min}(10^3,\frac{H \times W-2}{2})$
• $1 \leq a_i,c_i \leq H (1 \leq i \leq N)$
• $1 \leq b_i,d_i \leq W (1 \leq i \leq N)$
• $(1,1),(H,W),(a_1,b_1),\dots,(a_N,b_N),(c_1,d_1), \dots,(c_N,d_N)$ はすべて異なる

出力

最小値を整数で出力してください。

サンプル

3 3 1
1 2 3 2

3

5 4 2
2 4 1 2
4 4 2 1

7

10 10 5
4 5 3 3
4 6 6 10
8 8 10 5
9 5 3 1
9 3 3 4

13