题目描述

在一个 $N$ 行 $M$ 列的网格平面上，某些格子放置了障碍物，其余格子是空地。一个小球初始位于第 $x$ 行第 $y$ 列的空地格子上。

该平面可以向四个方向（上、下、左、右）倾斜。在每个时刻，平面以某个固定方向倾斜，小球会受到沿倾斜方向的力。小球可以选择顺着力滑动到相邻的空地格子，或者启动磁力制动器让自己停在原地不动。如果相邻格子是障碍物或超出网格边界，小球不能向该方向移动。

已知 $K$ 个连续的时间段，每个时间段内平面倾斜方向保持不变。请计算小球在所有时间段内能够滑行的最大总距离（即经过的格子数）。

输入格式

第一行包含 $5$ 个整数 $N$, $M$, $x$, $y$ 和 $K$。$N$ 和 $M$ 表示网格大小，$x$ 和 $y$ 表示小球初始位置（行号和列号），$K$ 表示时间段数目。

接下来 $N$ 行，每行 $M$ 个字符，描述网格。第 $i$ 行第 $j$ 列的字符若为 .，则表示空地；若为 x，则表示障碍物。

接下来 $K$ 行，每行三个整数 $s_i$, $t_i$, $d_i$，表示在时间区间 $[s_i, t_i]$ 内平面向 $d_i$ 方向倾斜。$d_i$ 取值为 $1$, $2$, $3$, $4$ 中的一个，依次表示上、下、左、右。输入保证区间连续，即 $s_1 = 1$，$s_i = t_{i-1} + 1$（$1 \lt i \le K$）。

输出格式

输出一行，包含一个整数，表示小球滑行的最大总距离。

样例

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

6

提示

【样例说明】

小球的滑行路线为：先向右滑动 $2$ 格，然后在第 $2$ 个时间段启动制动器停住 $1$ 步，再向上滑动 $1$ 格，最后向左滑动 $2$ 格，总计 $6$ 格。

【数据范围】

$50\%$ 的数据中，$1 \le N, M \le 200$，$T \le 200$；

$100\%$ 的数据中，$1 \le N, M \le 200$，$K \le 200$，$T \le 40000$。

其中 $T = t_K$ 表示总时间。