题目描述

绘画家小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

提示

没有写明提示

题目来源

鸣谢Claris上传试题