Mr. Turtle 喜欢在家里用白板画画。有一天他正在画画时，记号笔没墨了！Mr. Turtle 随后发现，在剩下的绘画过程中，这支记号笔表现得像一块橡皮擦。

Mr. Turtle 心中已经构思好了最终画作的样子。他提前一步步规划好了整幅画。Mr. Turtle 的计划是一系列指令：up（上）、down（下）、left（左）或 right（右），并带有相应的距离。他从白板的左下角开始作画。考虑第一个图中的 $6 \times 8$ 白板和指令序列。如果记号笔在时间步 17 没墨，白板看起来会像第二个图（数字表示记号笔在每个单元格的时间步）。注意，它会在时间步 17 留下标记，但在时间步 18 不会。

Mr. Turtle 想知道他的记号笔最早和最晚可以在什么时间步没墨，且他仍然能得到心中预想的画作。你能帮帮他吗？注意，时间步 0 是记号笔接触白板之前的时刻。记号笔在时间步 0 没墨也是有效的。

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。输入的第一行包含 3 个空格分隔的整数 $h, w$ 和 $n$ ($1 \le h, w, n \le 1,000,000, w \cdot h \le 1,000,000$)，其中 $h$ 和 $w$ 分别是白板的高度和宽度，$n$ 是 Mr. Turtle 计划中的指令数量。

接下来的 $h$ 行，每行包含恰好 $w$ 个字符，每个字符要么是 '#'，要么是 '.'。这是 Mr. Turtle 心中的图案，其中 '#' 是标记单元格，'.' 是空白单元格。

接下来的 $n$ 行，每行包含一个指令，格式为 “direction distance”，direction 和 distance 之间有一个空格，行内没有其他空格。direction 恰好是集合 {up, down, left, right} 中的一个，保证全为小写。distance 在 1 到 1,000,000 之间（包含边界）。指令必须按顺序执行。保证没有任何指令会让记号笔移出白板。

输出格式

输出两个整数，第一个是记号笔没墨前可以经过的最小时间步，第二个是最大时间步，且 Mr. Turtle 最终仍能得到目标画作。这两个数字都不应大于记号笔在白板上的最后一个时间步，因此如果记号笔可以运行到最后并仍然画出目标画作，请使用记号笔在白板上的最后一个时间步。如果无法得到目标画作，输出 -1 -1。

样例

样例输入 1

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

样例输出 1

20 20

样例输入 2

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

样例输出 2

17 17

样例输入 3

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

样例输出 3

-1 -1

样例输入 4

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

样例输出 4

0 1

Figure 1. 6x8 白板和指令序列