God Game

Taeyoung is addicted to games. He fell for a game called Legend of League, stopped studying, and filled his days with it. Junhyung, who found that pathetic, decided to build a god game himself and pull Taeyoung out of Legend of League.

Here is the game Junhyung built. The board is an $N\times M$ rectangle that lies in the first quadrant of the coordinate plane with one vertex at the origin. Both $N$ and $M$ are integers. The goal is to move a ball that starts at $(startX, startY)$ at time $t=0$ to $(endX, endY)$. All of these are integer coordinates. At each integer time $t$, Taeyoung does one of the following two things.

1. Leave the ball where it is for 1 second.
2. If the ball is at $(x, y)$, move it for 1 second at a speed of 1 cell per second to one of $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, $(x, y-1)$. The destination must be a position where the ball is allowed to be.

At every moment the ball's coordinates $(x, y)$ must satisfy $0\leq x\leq N$ and $0\leq y\leq M$. Even among the coordinates inside that range there can be positions where the ball is not allowed to be. Note that at any time $t$, at least one of the ball's $x$ coordinate and $y$ coordinate is an integer.

That alone would make the game too easy, so Junhyung put $K$ moving obstacles into some of the stages. Obstacle $i$ starts at the integer coordinate $(x\_i, y\_i)$ at $t=0$ and travels clockwise around a square whose side is the integer $a\_i$ ($1\leq a\_i\leq 5$) at a constant speed of 1 cell per second. Here $(x\_i, y\_i)$ is the lower left vertex of that square. For example, if $a\_i=2$ the obstacle follows the path

$(x\_i, y\_i)\to (x\_i, y\_i+1)\to(x\_i, y\_i+2)\to (x\_i+1, y\_i+2)\to (x\_i+2, y\_i+2)\to (x\_i+2, y\_i+1)\to (x\_i+2, y\_i)\to (x\_i+1, y\_i)\to (x\_i, y\_i)\to\cdots$

with a period of 8 seconds. Every point on an obstacle's path stays inside the board, but the path may run through cells where the ball is not allowed, and two obstacles may share a path. If the ball and an obstacle are at the same coordinate at some time $t$, the game is over. Here $t$ does not have to be an integer, and the point where the ball meets the obstacle does not have to be an integer coordinate.

Junhyung finished the game and handed it to Taeyoung, calling it a god game. The game was very hard, and Taeyoung played his heart out but got stuck on the third stage. We cannot play in his place, but for poor Taeyoung we can at least work out the minimum time it takes to clear a given stage.

Spacing out at the very start and losing, or getting hit by an obstacle the moment the ball reaches the destination, would be too unfair, so the merciful Junhyung never built such a case. In other words, the paths of the $K$ obstacles pass through neither the start nor the destination.

The first line contains the board size $N$ and $M$ ($1\leq N, M\leq 50$). The next $N+1$ lines describe the board. If the $j$-th character of the $i$-th line is ., the ball is allowed to be at $(i-1, j-1)$; if it is #, the ball is not allowed to be at $(i-1, j-1)$. S is the start and E is the destination. The next line contains the number of obstacles $K$ ($0\leq K\leq (N+1)(M+1) - 2$). Each of the next $K$ lines contains the integers $a\_i$, $x\_i$, $y\_i$ ($1\leq a\_i\leq 5$, $0\leq x\_i\leq N-a\_i$, $0\leq y\_i\leq M-a\_i$) describing one obstacle.

Print the minimum time Taeyoung needs to clear the game. If he can never clear it, print INF.

On the board given in the input format, the downward direction is $+x$ and the rightward direction is $+y$. There may also be no obstacles at all ($K=0$).

The figure above shows a $1\times 7$ board with four obstacles of side 1 standing in a row. No matter how well the ball is moved, it cannot get past the stretch covered by those four obstacles. In that case there is no way to clear the game. With only three obstacles in the same spot, the right timing takes the ball through that stretch and clears the game.