题目描述
你现在正在参加一次军事模拟训练。训练的地图是一个网格图，包含$n$行和$m$列。每个网格要么是空的，要么是障碍物。空格可能包含一件武器。设$(x,y)$是第$x$行和第$y$列上的网格。如果你在网格$(x,y)$处，则你可以移动到网格$(x',y')$，当且仅当$1\leq x'\leq n,1\leq y'\leq m,|x-x'|+|y-y'|=1$，并且$(x',y')$不是障碍。行动需要一秒钟。
你目前位于网格$(px,py)$，敌人位于$(bx,by)$。除非你达到网格$(bx,by)$，否则敌人永远不会移动。如果你达到网格$(bx,by)$，那么你就会被敌人消灭，并且输掉这次训练。
你一开始没有武器，但$k$个武器被放置在地图中。每件武器都被放置在一个空格中，武器所在的格子两两不同，如果你到达一个有武器的各自，你就可以装备这件武器。第$i$-件武器的攻击距离为$d_i$，这意味着如果你目前在$(x,y)$，并且装备了这件武器，他可以攻击任何网格$(x',y')$ 当且仅当 $\sqrt{(x-x')^2+(y-y')^2}\leq d_i$。并且这会立即消灭网格$(x',y'$)处的敌人。装备武器不需要时间，攻击也不需要时间。你可以装备任意数量的武器，随时使用。
请你计算你消灭敌人的最小时间，或者输出这是不可能的任务。
输入格式
输入包含多组数据。
第一行包含一个整数$T$，表示数据的组数。
对于每组数据，第一行包含三个整数$n,m,k$。
第二行包含四个整数$px,py,bx,by$，表示你和敌人的位置。保证$px\neq bx$或$py\neq by$。
接下来$n$行，每一行都包含一个长度为$m$的字符串。第$i$行上的第$j$个字符是“$\texttt{.}$”或“$\texttt{#}$”，表示第$i$行，第$j$列是空网格或障碍物。
接下来$k$行中的第$i$行包含三个整数$x_i,y_i,d_i$，表示武器$i$位于$(x_i,y_i)$并且具有攻击距离$d_i$。
输出格式
对每组数据输出一行，代表消灭敌人需要花费的最小时间，或者输出$-1$代表不可能。
输入样例1
2
4 4 2
1 1 4 4
...#
..##
.###
###.
1 1 3
1 3 5
3 3 1
3 3 1 1
.##
###
##.
3 3 1输出样例1
2
-1样例$2$见下发文件。
样例解释：
在$(1,1)$拿起攻击距离为$3$的武器，之后花费$2$的时间走到$(2,2)$，就可以攻击$(4,4)$
对于第二组，不存在攻击的方法
数据范围
对于$30\%$的数据，$n,m\leq 20$,$T\leq 5$；
对于$60\%$的数据，$n\leq 100$,$T\leq 5$；
对于所有数据，$1\leq T\leq 10, 1\leq n,m\leq 400,1\leq k\leq n\cdot m$,保证$\sum{nm}\leq 1.6\times 10^5$，保证所有坐标合法，武器攻击距离$0\leq d_i\leq 10^9$，不会有两个武器在同一个格子，你初始位置和敌人的位置不会重合。
请注意特殊的时间空间限制。
