[NOI2005] 瑰丽华尔兹

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？

众所周知，跳华尔兹时最重要的是有好的音乐。世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼·布德曼·T.D.·柠檬·1900，朋友们都叫他 1900。1900 在 20 世纪的第一年出生在往返欧美的邮轮弗吉尼亚号上，刚出生就被抛弃，成了孤儿。他孤独地成长在这艘船上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他，也点化了他不可思议的钢琴天赋：从未有人教，从没看过乐谱，他却能凭着感觉弹出最沁人心脾的旋律。

1900 毕竟还是个孩子，有着和一般男孩一样的好奇和调皮，只不过更多一层浪漫色彩。在一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮剧烈摇摆。新萨克斯手马克斯·托尼晕船了，1900 招呼他一起坐上舞厅里的钢琴，然后松开了固定钢琴的闸——于是钢琴随着海轮的倾斜滑动起来。1900、钢琴、邮轮，随着旋律一起跳起了华尔兹，随着「嘣嚓嚓」的节奏，托尼的晕船症也奇迹般地消失了。

别忘了艾米丽，她可没闲着：她必须在适当的时候施展魔法，不让钢琴撞上舞厅里的家具。

不妨认为舞厅是一个 $n$ 行 $m$ 列的矩阵，某些方格上堆放了家具，其余是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅。时间从 $1$ 开始计量，每个时刻：

若艾米丽不施魔法，钢琴会随着船体倾斜的方向向相邻的方格滑动一格；
若艾米丽施魔法，钢琴原地不动。

艾米丽知道每段时间内船体的倾斜情况，她想让钢琴在舞厅里滑行的总路程尽量长，这样 1900 会非常高兴，也有利于治疗托尼的晕船。可她还太小，不会算，希望你能帮助她。

输入格式

第一行包含五个整数 $n, m, x, y, k$ 。其中 $n, m$ 描述舞厅的大小， $(x, y)$ 为钢琴的初始位置（第 $x$ 行第 $y$ 列）。船体的倾斜情况按时间区间描述， $k$ 表示区间的数目。

接下来 $n$ 行，每行 $m$ 个字符，描述舞厅里的家具。第 $i$ 行第 $j$ 列的字符若为 . 则表示该位置是空地，若为 x 则表示有家具。

接下来 $k$ 行，顺序描述 $k$ 个时间区间，第 $i$ 行包含三个整数 $s_i, t_i, d_i$ ，表示在时间区间 $[s_i, t_i]$ 内船体都向 $d_i$ 方向倾斜。 $d_i \in \{1,2,3,4\}$ ，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。

输入保证区间是连续的，即

s_1 = 1,\qquad s_i = t_{i-1}+1\ (1 < i\le k),\qquad t_k = T,

其中 $T$ 为总时长。

输出格式

输出一行一个整数，表示钢琴滑行的最长距离（即经过的格子数）。

样例输入

4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

样例输出

样例解释

舞厅为 $4$ 行 $5$ 列，钢琴初始位于第 $4$ 行第 $1$ 列。三个时间区间依次为： $[1,3]$ 向东、 $[4,5]$ 向北、 $[6,7]$ 向西。

一种最优方案是让钢琴依次经过

(4,1)\to(4,2)\to(4,3)\to(3,3)\to(2,3)\to(2,2)\to(2,1),

即在 $[1,3]$ 内向东滑动 $2$ 格（其中一个时刻施魔法停留），在 $[4,5]$ 内向北滑动 $2$ 格，在 $[6,7]$ 内向西滑动 $2$ 格，总距离为 $6$ 。可以验证不存在更长的方案。

数据范围

对于所有测试数据：

$1\le n, m\le 200$ ；
$1\le x\le n$ ， $1\le y\le m$ ，且初始位置为空地；
$1\le k\le 200$ ；
$1\le s_i\le t_i$ ， $d_i\in\{1,2,3,4\}$ ；
总时长 $T\le 40000$ 。

来源与许可

本题为 CCF NOI 2005 试题「瑰丽华尔兹」，题面与测试数据整理自 BZOJ 1499。

样例 1

输入

4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3