时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld
题目描述
“他的邪恶乃是一个传奇。他是亡灵天灾的君王，是符文圣剑霜之哀伤的主人，是艾泽拉斯世界一切自由族类的大敌。
巫妖王是无与伦比的强大力量与极端冷酷的化身，他比寒冰更加寒冷的灵魂已经被他的宏大计划彻底吞噬。
在这个计划中，他将毁灭世界上的全部生灵。
巫妖王-阿尔萨斯已经启动了可能导致艾泽拉斯所有生灵毁灭的计划，他的天灾军团和驱役亡灵的强大力量将横扫整个世界。
我们可以将艾泽拉斯视为n∗m的矩阵，其中
S：寒冰王座，起点
T：暴风城，终点
∗：平原，天灾军团可以到达的地方
#：沼泽，天灾军团无法到达的地方
在地图上存在着 k 个传送门，借助传送门，可以瞬间（不花费时间地）从传送门的任一端到达另一端
天灾军团每小时可以向其周围4个方向移动一格（上下左右），为了保证天灾军团随时保持最高战斗力，巫妖王命令军队每行军8小时，就原地休息1小时。
现在巫妖王率领他的天灾军团从S出发，问最快多久可以到达T？
输入描述:
第1行两个整数n,m (1<= n, m<=1000 , 且n,m不同时等于1)
第2到n+1行每行含有m个字符，其中：
第n+2行有一个整数k（0 <= k <= 10）
随后k行，每行包含4个整数x1,y1,x2,y2表示传送门两端的坐标(x1,y1),(x2,y2)
（1 <= x1,x2 <= n ，1<= y1,y2<= m）
（注意，传送门也可以直接存在于S和T之间,同时，同一个传送门的两端可能在同一个位置，但是一个地点不可能有多个传送门的一端）
输出描述:
输出仅一行，表示巫妖王到达暴风城的最短时间，如果无法到达，则输出-1