[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

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