409528: GYM103624 G Current Objective: Survive

G. Current Objective: Survivetime limit per test7.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You're operating a merchant ship when your second mate gives you some troubling news: you've sailed right into pirate-infested waters, headed by none other than Captain Crawfish!

The sea can be represented as an $$$N$$$ by $$$M$$$ grid with two types of characters: "." representing open water, and "#" representing land (i.e. you cannot sail on it). Your second mate has also determined the locations of all nearby pirate ships.

You are given the location of each pirate ship represented by the coordinates $$$(x_i, y_i)$$$, the direction it's facing (north, east, south, or west), and the number of locations the ship patrols, $$$k_i$$$. Pirate ships behave in the following manner:

• Each pirate ship starts in the given position.
• At each minute, each pirate ship moves one unit in the direction it is facing. It is guaranteed that this move is possible, that is, it is in bounds and is not occupied by land.
• When the pirate ship has moved exactly $$$k_i - 1$$$ times, meaning it has patrolled its designated $$$k_i$$$ locations, it turns 180 degrees. (The turn takes no time).
• The pirate ship follows the same process in the reverse direction, traveling one unit every minute.
• When the pirate ship reaches its starting location, it once again turns 180 degrees, taking no time, and repeats the process.

*Note that a ship patrolling exactly 1 location will never move.

Your ship starts in the upper left-hand corner, represented by coordinates $$$(1, 1)$$$, and you need to get to location $$$(N, M)$$$, the lower right-hand corner. In any minute, you can either move to adjacent coordinates (north, south, east, or west) or stay where you are. (Assume north is represented by the upwards direction.) You cannot move to an adjacent coordinate if it is occupied by land, and you cannot leave the bounds of the grid (legend has it the Kraken lurks beyond the bounds of the grid). If you move to a coordinate at the same time a pirate ship does, your ship is captured!

What's the minimum amount of time, in minutes, you need to traverse the waters without being captured and reach position $$$(N, M)$$$? If no path exists, output $$$-1$$$ and prepare to walk the plank!

Input

The first line contains two integers $$$N, M, K$$$ representing the number of rows, number of columns, and the number of pirates, respectively. $$$(2 \le N \le 100, 2 \le M \le 100, 1 \le K \le 2000)$$$

The next $$$N$$$ lines contain the contents of the sea, where "." represents open water, and "#" represents land. It is guaranteed that the locations $$$(1, 1)$$$ and $$$(N, M)$$$ will have water.

The next $$$K$$$ lines describe Captain Crawfish's pirate ships: each line contains three integers $$$x_i, y_i, k_i$$$, followed by a character $$$N, S, E,$$$ or $$$W$$$, where:

• $$$(x_i, y_i)$$$ is the starting location of the pirate ship. $$$(1 \le x_i \le N, 1 \le y_i \le M)$$$. No pirate ship will start at location $$$(1, 1)$$$.
• $$$k_i$$$ represents the number of locations the pirate ship patrols. $$$(1 \le k_i \le 8)$$$
• The character represents the direction the pirate ship faces initially. (N-north, S-south, E-east, W-west).

Output

Print out the minimum amount of time required to get from the upper left-hand corner $$$(1, 1)$$$ to the bottom right-hand corner $$$(N, M)$$$ without being captured. If no such path is possible, print $$$-1$$$.

ExamplesInput

5 10 2
...####...
...####...
..........
...####...
...####...
3 3 7 E
3 4 7 E

Output

22

Input

5 10 2
...####...
...####...
..........
...####...
...####...
3 3 6 E
3 4 6 E

Output

-1

Note

For the sake of simplicity, assume all ships move instantaneously. That is, you will be captured if and only if you move to some location at the same time as a pirate ship, regardless of where you or the pirate ship came from.

Multiple pirate ships can coexist in the same location.