在一个 n 乘以 m 大小的迷宫当中，你必须依序执行很多项搬东西的任务。每一个任务都有起始点 A 以及终点 B 。行动的时候如果手上没有搬东西，就不会耗费任何体力，但是如果手上有东西，那么耗费的体力就是以移动「一格」消耗一单位的体力来计算。而所谓移动「一格」是指从目前迷宫中的位置往东、南、西、北四个方向前进一步的长度。有趣的是，经过你的缜密观察，尽管迷宫内部相当复杂，它一定会遵守「右手定则」，也就是说，只要摸着右手边的墙壁不断地往前行走，终究可以踏遍迷宫中的每一块空地，并且连所有空地周围看得到的围墙部分都被你摸过了。聪明的你在执行每一个任务的时候，都会挑选最短路径搬运指定物品。请问执行完所有任务以后你所需要耗费的最少体力总和是多少？
输入的第一行包含三个正整数 n, m, Q 。接下来我们用 n 列(rows)每一列以 m 个字元来表示迷宫。迷宫内部标注 '.' 的部份是空地，标记 '#' 的部份是墙。迷宫最外围一定都是墙壁。接下来有 Q 列分别代表 Q 项任务的起点和终点，每一列包含四个整数 x, y, z, w ，代表每一项任务从 (x, y) 出发，并且在 (z, w) 结束。注意到迷宫的编号方式以左上角为 (0, 0) ，右下角为 (n-1, m-1) 。你可以假设输入的所有座标都会是空地的座标。 迷宫里面不会有2x2的空地出现。 (edit: 11/16 10:17am)
请输出依序执行完所有任务后所需要耗费的最小体力。
10 10 6 ########## #......#.# #####.#..# #####...## ###.#.#.## ###.#.#..# ##...#..## ##.#..#.## #...#....# ########## 1 1 1 1 3 6 1 3 3 6 6 3 2 8 2 5 2 5 2 8 7 4 6 2
30
测试资料说明
占总分至少 30% 的测试资料中满足 5<= n, m <=30
占总分至少 40% 的测试资料中满足 0 <= Q <= 500
对于所有的测试资料，满足 5<= n, m <=250, 0 <= Q <= 50000 ，并且答案一定不会超过 2147483647 。