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$.
Input
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$ spaceseparated 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
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
