the world
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}咲夜拥有时停的力量。现在有一个 n \times m 的地图，其中有 k 个幽灵在游走，每个幽灵在奇数秒开始时会传送到 \left( x_{1i},y_{1i}\right)，偶数秒开始时会传送到 \left(x_{2i},y_{2i}\right)。
\hspace{15pt}咲夜在每秒开始时都会移动到相邻的四个格子之一，且移动时不会接触到幽灵（可以移动到上一秒幽灵所在的位置）。
\hspace{15pt}她可以使用最多一次时停，使得所有幽灵持续 2 秒呆在原地不动。
\hspace{15pt}时间从第 1 秒开始计算（幽灵初始位于 \left( x_{1i},y_{1i}\right)），咲夜初始位于 \left(1, 1 \right)，她想知道在不能与幽灵处于同一格子的条件下，她最少需要多少秒才能移动到 \left(n, m \right)？

输入描述:

\hspace{15pt}第一行输入三个整数 n, m, k \left(1 \leqq n, m \leqq 1000, 1 \leqq k \leqq n \times m \right)。
\hspace{15pt}之后 k 行，每行输入四个整数 x_{1i},y_{1i},x_{2i},y_{2i} \left(1 \leqq x_{1i},x_{2i} \leqq n, 1 \leqq y_{1i},y_{2i} \leqq m \right)。特殊的，保证不会有幽灵初始位于 \left(1, 1 \right)。

输出描述:

\hspace{15pt}如果咲夜无法到达 \left(n, m \right)，输出 -1；否则输出一个整数，代表所需的最短时间。
示例1

输入

复制 
1 4 1
1 2 1 3

输出

复制 
3
示例2

输入

复制 
1 4 1
1 3 1 2

输出

复制 
-1