遗迹传送

题目背景

考古队在沙漠深处发现了一座古代遗迹。遗迹被划成整齐的方格，小 P 需要从遗迹的西北角入口一直走到东南角的出口。遗迹里还残存着一些成对的传送门，这也许能让路变得短一些。

题目描述

遗迹可以看成一张 $n$ 行 $m$ 列的方格图，第 $i$ 行第 $j$ 列的格子记作 $(i,j)$。

每个格子有两种状态：可通行的地面，用字符 . 表示；石柱，用字符 # 表示。石柱无法进入。

遗迹中还残存着 $p$ 对传送门。每一对传送门占据两个不同的地面格子，并且每个格子至多属于一对传送门。当你走进某个传送门所在的格子时，会立刻被传送到与它同属一对的另一个传送门格子中，这次落地不会引发新的传送。也就是说，传送只会在你主动走进某个传送门格子的那一步发生。

小 P 从 $(1,1)$ 出发。每一步，他可以走向上、下、左、右四个方向中相邻的一个格子，只要该格子存在且不是石柱。如果走到的格子上有传送门，那么他会被立刻传送到同对的另一格，这一步仍然只算作一步。

请你求出小 P 到达 $(n,m)$ 所需的最少步数。如果无论如何都无法到达，输出 $-1$。

保证 $(1,1)$ 与 $(n,m)$ 都是地面，并且它们都不属于任何一对传送门。

输入格式

从标准输入读入数据。

第一行三个整数 $n,m,p$，依次表示行数、列数、传送门的对数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述遗迹的一行，字符只会是 . 或 #。

接下来 $p$ 行，每行四个整数 $r_1,c_1,r_2,c_2$，表示一对传送门，其中格子 $(r_1,c_1)$ 与格子 $(r_2,c_2)$ 互相连通。保证这两个格子互不相同、都是地面，并且所有传送门涉及的格子两两不同。

输出格式

输出到标准输出。

一行一个整数，表示到达 $(n,m)$ 的最少步数；若无法到达，输出 $-1$。

样例 1 输入

3 3 0
...
.#.
...

样例 1 输出

4

样例 1 解释

没有传送门。从 $(1,1)$ 出发，向右、向下、向右、向下，共 $4$ 步到达 $(3,3)$。这也是最少步数。

样例 2 输入

5 5 1
.....
.#.#.
.#.#.
.#.#.
.....
3 1 3 5

样例 2 输出

4

样例 2 解释

若不走传送门，只能沿着边界绕行 $8$ 步。若从 $(1,1)$ 向右下的方向走到 $(3,1)$，就会立刻被传送到 $(3,5)$，只需 $4$ 步。

样例 3 输入

1 5 0
..#..

样例 3 输出

-1

数据范围

测试点编号	$n,m$	$p$	特殊性质
$1\sim 3$	$\le 10$	$\le 5$	无
$4\sim 6$	$\le 100$
$7\sim 10$	$\le 1000$		A
$11\sim 14$			B
$15\sim 17$			C
$18\sim 20$			无

特殊性质 A：$p=0$。

特殊性质 B：遗迹中没有石柱，即所有格子都是地面。

特殊性质 C：每对传送门连接的两个格子相邻。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。