2012大逃亡

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

       传说中的2012快到来了,为了逃避灾难,鱼头找到了一个安全地带。可是当他带领acm集训队的同学们来到时,发现因为地震和火山爆发,许多地方已经不能通行了。还好鱼头有先见之明,在一些地方放置了传送门。可不幸的是,传送门同样应为地震,部分功能已经失灵。现在知道:传送门是一对对的,其中一个是主门,另一个是副门,只能从主门传送到副门,不能反过来。因损坏,只要当人走到主传送门上时,它就会不受控制的将人传到副门。因为传送需要能量,所以对某个固定的传送门只能传送固定次数。同时不能走出所在区域(外面不安全)。现已知此处的地图和传送门坐标,鱼头想知道最少几步能从起点走到目的地?

Input

第一行是一个整数t,表示测试数据个数。 对每组数据: 第一行2个整数n,m,表示地图边长。0 < n、m<=10(地图坐标从1算起) 接下来n行每行m个元素,’.’表示此处安全,’#’表示此处危险(走上去就挂了),’s’表示鱼头所在位置,’e’表示目的地。地图外区域均为’#’。 接下来一个整数k,表示传送门数目。0<=k<=8; 接下来k行每行5个整数,x1,y1,x2,y2,s对应主传送门坐标和副传送门坐标,s为次传送门一共能传送几次。0 < s <= 2 任意2个主传送门坐标不可能相同,主传送门不会是目的地。1 <= x1 <= n,1 <= y1 <= m。 鱼头每次只能走向相邻的4个坐标中,每移动一次需1的时间,传送一次需1的时间。

Output

鱼头从所在位置走到安全地带所需时间,无法到达或走出地图输出-1。

Sample Input

2
2 2
s.
.e
0
3 3
s.#
.#.
.#e
1
1 2 2 3 2

Sample Output

2
3

Hint

Source

StSky

提交代码