题目描述
你现在正在参加一次军事模拟训练。训练的地图是一个网格图，包含n行和m列。每个网格要么是空的，要么是障碍物。空格可能包含一件武器。设(x,y)是第x行和第y列上的网格。如果你在网格(x,y)处，则你可以移动到网格(x′,y′)，当且仅当1≤x′≤n,1≤y′≤m,|x−x′|+|y−y′|=1，并且(x′,y′)不是障碍。行动需要一秒钟。
你目前位于网格(px,py)，敌人位于(bx,by)。除非你达到网格(bx,by)，否则敌人永远不会移动。如果你达到网格(bx,by)，那么你就会被敌人消灭，并且输掉这次训练。
你一开始没有武器，但k个武器被放置在地图中。每件武器都被放置在一个空格中，武器所在的格子两两不同，如果你到达一个有武器的各自，你就可以装备这件武器。第i-件武器的攻击距离为di，这意味着如果你目前在(x,y)，并且装备了这件武器，他可以攻击任何网格(x′,y′) 当且仅当 √(x−x′)2+(y−y′)2≤di。并且这会立即消灭网格(x′,y′)处的敌人。装备武器不需要时间，攻击也不需要时间。你可以装备任意数量的武器，随时使用。
请你计算你消灭敌人的最小时间，或者输出这是不可能的任务。
输入格式
输入包含多组数据。
第一行包含一个整数T，表示数据的组数。
对于每组数据，第一行包含三个整数n,m,k。
第二行包含四个整数px,py,bx,by，表示你和敌人的位置。保证px≠bx或py≠by。
接下来n行，每一行都包含一个长度为m的字符串。第i行上的第j个字符是“.”或“#”，表示第i行，第j列是空网格或障碍物。
接下来k行中的第i行包含三个整数xi,yi,di，表示武器i位于(xi,yi)并且具有攻击距离di。
输出格式
对每组数据输出一行，代表消灭敌人需要花费的最小时间，或者输出−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≤20,T≤5；
对于60%的数据，n≤100,T≤5；
对于所有数据，1≤T≤10,1≤n,m≤400,1≤k≤n⋅m,保证∑nm≤1.6×105，保证所有坐标合法，武器攻击距离0≤di≤109，不会有两个武器在同一个格子，你初始位置和敌人的位置不会重合。
请注意特殊的时间空间限制。
