在与boss的最终决战之后，小蓝来到了冒险的最后一关，在他面前有一个n*m的迷宫，迷宫中道路用 . 表示，墙壁则由 # 表示。小蓝初始在[1,1]的位置，他只有到达[n,m]才能开启最终的宝藏。小蓝现在迫不及待的想要开启宝藏，所以他想最短的时间内走出迷宫。现在迷宫内有一种特殊的装置–弹射器”。弹射器的格子用 * 表示。当走到有弹射器的一格时，小蓝必须选择一个方向，弹射器会让他沿着这个方向弹射x个距离，不同弹射器的弹射距离可以不同。弹射后的格子如果超过迷宫边界或者是墙壁则不能选择这个方向。小蓝现在可以向上下左右四个方向走，每走一个格子需要消耗一个单位时间，弹射则不消耗时间。求最短需要多少时间小蓝才能走出迷宫。如果无法到达终点，输出-1。
弹射器的数量，位置和弹射距离将在输入中给出。起点和终点一定不是弹射器。

第一行两个整数n, m，接下来n行，每行m个只包含'.’，’*”，'#'的字符描绘迷宫。
接下来一行一个整数k，下面的k行每行三个整数x， y， w表示在[x, y]格子的弹射器能弹射的距离。( 2≤n≤3000 ,2≤m≤3000, n*m≤500000,0≤k , w在int范围内)

一行一个整数

-1

2023河南萌新联赛(一) * bfs