Whiteboard

Mr. Turtle likes drawing on the whiteboard at home. One day, in the middle of a drawing, his marker dried out. From that moment on the marker worked like an eraser: every cell it passed over was wiped blank instead of being marked.

Mr. Turtle already knows the picture he wants. He plans the whole drawing in advance as a list of commands, and each command is a direction (up, down, left or right) together with a distance. He starts in the bottom left corner of the whiteboard.

Time is counted in timesteps. Timestep 0 is the moment before the marker touches the board. At timestep 1 the marker sits on the starting cell, and every single cell of movement advances the clock by one timestep. If $d$ is the sum of all command distances, the last timestep at which the marker is on the board is $1 + d$.

Suppose the marker dries out at timestep $T$. At every timestep $t$ with $1 \le t \le T$ the marker marks the cell it sits on, and at every timestep $t > T$ it wipes that cell blank, whatever was drawn there before. A marker that dries out at timestep 17 still marks at timestep 17 but erases at timestep 18. The value $T = 0$ is allowed and leaves the board empty.

Given the size of the whiteboard, the target picture and the plan, find the smallest and the largest $T$ for which the final board matches the target picture.

The figure shows a $6 \times 8$ whiteboard with a plan of five commands, and the board that is left when the marker dries out at timestep 17. The number written in a cell is the timestep at which the marker sits on that cell.

The first line has three integers $h$, $w$ and $n$ ($1 \le h, w, n \le 1\,000\,000$, $h \cdot w \le 1\,000\,000$). Here $h$ and $w$ are the height and the width of the whiteboard, and $n$ is the number of commands.

Each of the next $h$ lines has exactly $w$ characters and describes the target picture from the top row to the bottom row. # is a marked cell and . is a blank cell.

Each of the next $n$ lines holds one command in the form direction distance, with a single space between the two parts and no other space on the line. The direction is exactly one of up, down, left, right, all in lower case. The distance is an integer between $1$ and $1\,000\,000$. The commands are carried out in the given order. No command moves the marker off the whiteboard.

Print two integers on one line: first the smallest, then the largest timestep at which the marker can dry out and still leave the target picture on the board. Neither value may exceed the last timestep at which the marker is on the board, so if the marker can stay wet for the whole plan, print that last timestep as the maximum. If the target picture cannot be produced, print -1 -1.