Whiteboard

Mr. Turtle loves drawing on his whiteboard at home. One day when he was drawing, his marker dried out! Mr. Turtle then noticed that the marker behaved like an eraser for the remainder of his drawing.

Mr. Turtle has a picture in his head of how he wants his
final drawing to appear. He plans out his entire drawing ahead
of time, step by step. Mr. Turtle’s plan is a sequence of
commands: *up*, *down*, *left* or
*right*, with a *distance*. He starts drawing in
the bottom left corner of his whiteboard. Consider the
$6 \times 8$ whiteboard
and sequence of commands in the first diagram. If the marker
runs dry at timestep $17$,
the board will look like the second diagram (the numbers
indicate the timestep when the marker is at each cell). Note
that it will make a mark at timestep $17$, but not at timestep $18$.

Mr. Turtle wants to know the earliest and latest time his marker can dry out, and he’ll still obtain the drawing in his head. Can you help him? Note that timestep $0$ is the moment before the marker touches the board. It is valid for a marker to dry out at timestep $0$.

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input will start with a line with $3$ space-separated integers $h$, $w$ and $n$ ($1 \le h,w,n \le 1\, 000\, 000, w \cdot h \le 1\, 000\, 000$) where $h$ and $w$ are the height and width of the whiteboard respectively, and $n$ is the number of commands in Mr. Turtle’s plan.

The next $h$ lines will
each consist of exactly $w$ characters, with each character
being either ‘`#`’ or ‘`.`’ . This is the pattern in Mr. Turtle’s head,
where ’`#`’ is a marked cell, and
‘`.`’ is a blank cell.

The next $n$ lines will
each consist of a command, of the form “*direction
distance*”, with a single space between the
*direction* and the *distance* and no other
spaces on the line. The *direction* will be exactly one
of the set $\{ \texttt{up},
\texttt{down}, \texttt{left}, \texttt{right} \} $,
guaranteed to be all lower case. The *distance* will be
between $1$ and
$1\, 000\, 000$ inclusive.
The commands must be executed in order. It is guaranteed that
no command will take the marker off of the whiteboard.

Output two integers, first the minimum, then the maximum
time that can pass before the marker dries out, and Mr. Turtle
can still end up with the target drawing. Neither number should
be larger than the last timestep that the marker is on the
board, so if the marker can run to the end and still draw the
target drawing, use the last timestep that the marker is on the
board. If it’s not possible to end up with the target drawing,
output `-1 -1`.

Sample Input 1 | Sample Output 1 |
---|---|

6 8 5 ........ ...#.... ######## #..#...# #..##### #....... up 3 right 7 down 2 left 4 up 3 |
20 20 |

Sample Input 2 | Sample Output 2 |
---|---|

6 8 5 ........ ........ ###.#### #......# #..##### #....... up 3 right 7 down 2 left 4 up 3 |
17 17 |

Sample Input 3 | Sample Output 3 |
---|---|

3 3 2 ... .#. ... up 2 right 2 |
-1 -1 |

Sample Input 4 | Sample Output 4 |
---|---|

2 2 4 .. .. up 1 right 1 down 1 left 1 |
0 1 |