G. Mysterious Maze
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Neo-Bot, an advanced pathfinder dog, is trapped in a 2D grid. He is at coordinates $$$(0, 0)$$$ and needs to get to $$$(x, y)$$$ to escape. There are also $$$M$$$ lines going from $$$(x1_i, y1_i)$$$ to $$$(x2_i, y2_i)$$$. These lines lie along the grid axes, so either both the x's or both the y's will be identical. Neo-Bot can only travel along the lines. Output how far Neo-Bot travels until he makes it to the end, or -1 if he never reaches there.

Input

Line 1: Three space-separated integers $$$X, Y, M$$$

Line 2 through $$$M+1$$$: $$$M$$$ lines of 4 space-separated integers: $$$x1_i, y1_i, x2_i, y2_i$$$. As stated above, in one of these two pairs ($$$x1_i$$$ & $$$x2_i$$$ and $$$y1_i$$$ & $$$y2_i$$$), both variables will have the same value. It is also guaranteed that at least one of these segments will pass through ($$$0, 0)$$$ and at least one of them will pass through $$$(X, Y)$$$.

Output

Line 1: One integer representing the distance Neo-Bot has to travel before he reaches his end coordinates, or -1 if he never does.

Example
Input
10 10 7
3 0 3 7
1 2 8 2
2 2 2 9
2 9 10 9
0 1 4 1
10 2 10 10
0 0 0 5
Output
22
Note

$$$1 ≤ M ≤ 150$$$

$$$1 ≤ x_i, y_i ≤ 1,000,000$$$