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)$.

tkms wants to travel from $(1,1)$ to $(H,W)$ on the grid as quickly as possible.

There are $N$ warps on the grid, and the $i(1 \leq i \leq N)$-th warp leads from $(a_i,b_i)$ to $(c_i,d_i)$. Warps cannot be traversed in reverse.

In $1$ action, tkms can do one of the following:

• Move $1$ cell in one of the four directions. That is, when at $(x,y)$, move to any $1$ of $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$.
• Pass through a warp.

When at the starting point of a warp, he may move in one of the four directions without passing through the warp.

He cannot move outside the grid.

Find the minimum number of actions needed to reach $(H,W)$ starting from $(1,1)$.

Input

$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$

• All inputs are integers.
• $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)$ are all distinct.

Output

Print the minimum value as an integer.

Sample

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