#4879. [Lydsy1705月赛]失控的数位板

内存限制:256 MiB 时间限制:30 Sec

题目描述

绘画家小Q正在他的数位板上作画。当他在作画的时候,他的设备突然故障了!此时他的笔变成了擦除模式。在小Q
的脑海中,有一副漂亮的图案,他希望最后能将它呈现在板子上。他按照自己的创作风格,一步一步地绘画。他每
一步只可能是4种指令上(up)下(down)左(left)右(right)中的一种,同时指定一个距离d,每秒往那个方向移动一
步。在创作的一开始,他的笔位于数位板的左下角,且任意时刻他的笔都不会离开数位板。考虑6*8的数位板以及
如下图所示的指令集,如果笔在第17秒末故障了,数位板最终会变成第二幅图的样子。
小Q想知道最早和最晚的时刻t,满足如果数位板在第t秒末故障了,最终显示出来的图案与他预想的一致。注意数
位板可以在第0秒末故障,此时小Q的笔还没有触碰到数位板。

输入格式

第一行包含三个正整数h,w,n(1<=h,w,n<=10^6,1<=w*h<=10^6),分别表示数位板的高度与宽度以及指令的条数。
接下来h行,每行w个字符
每个字符要么是“#”,要么是“.”。表示小Q预想的效果,其中“#”表示有颜色,“.”表示空白。
接下来n行
每行一个字符串s和一个正整数d(1<=d<=10^6),分别表示方向和距离,输入数据保证操作不会使笔离开数位板。

输出格式

输出一行两个整数x与y,其中x表示最小的合法的t,y表示最大的合法的t
注意y不能超过最后一条指令执行完毕时的时间。若无解则输出“-1 -1”。

样例

样例输入


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

样例输出


			
17 17

数据范围与提示