题目描述

乌龟先生喜欢在家里的白板上画画。有一天，当他正在画画时，他的记号笔突然没墨了！乌龟先生随后注意到，在他接下来的绘画过程中，这支记号笔表现得像一块橡皮擦。

乌龟先生脑海中有一幅他想要完成的最终画作。他事先一步一步地规划好了整个绘画过程。乌龟先生的计划是一系列指令：向上（up）、向下（down）、向左（left）或向右（right），并附带一个距离（distance）。他从白板的左下角开始绘画。考虑第一张图中的 $6 \times 8$ 白板和指令序列。如果记号笔在第 $17$ 个时间步没墨，白板将看起来像第二张图（数字表示记号笔在每个格子时的时刻）。注意，它会在第 $17$ 个时间步留下痕迹，但在第 $18$ 个时间步不会。

:::align{center} :::

乌龟先生想知道，为了最终得到他脑海中的画作，他的记号笔最早和最晚可以在什么时间没墨。你能帮助他吗？注意，时间步 $0$ 是记号笔接触白板之前的时刻。记号笔在时间步 $0$ 没墨是允许的。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含三个空格分隔的整数 $h$、$w$ 和 $n$（$1 \leq h, w, n \leq 1{,}000{,}000$，$w \cdot h \leq 1{,}000{,}000$），其中 $h$ 和 $w$ 分别是白板的高度和宽度，$n$ 是乌龟先生计划中的指令数量。

接下来的 $h$ 行，每行恰好包含 $w$ 个字符，每个字符要么是 #，要么是 .。这是乌龟先生脑海中的图案，其中 # 表示被标记的格子，. 表示空白格子。

接下来的 $n$ 行，每行包含一条指令，格式为“$direction$ $distance$”，指令和距离之间用一个空格分隔，行内没有其他空格。$direction$ 必须是集合 $\{up, down, left, right\}$ 中的一个，保证为小写。$distance$ 在 $1$ 到 $1{,}000{,}000$ 之间（包含）。指令必须按顺序执行。保证没有任何指令会使记号笔离开白板。

输出格式

输出两个整数，第一个是最小时间，第二个是最大时间，表示记号笔可以在该时间没墨，并且乌龟先生最终仍能得到目标画作。这两个数字都不应大于记号笔最后一次停留在白板上的时间步。因此，如果记号笔可以一直运行到最后并且仍然得到目标画作，则使用记号笔最后一次停留在白板上的时间步作为最大值。如果无法得到目标画作，则输出 $-1$ $-1$。

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

20 20

3 3 2
...
.#.
...
up 2
right 2

-1 -1

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

0 1

提示

翻译由 DeepSeek V3.2 完成