Description

Assume the ballroom is an $N$-by-$M$ grid. Some cells have furniture piled on them, and the rest are empty. The piano can slide on empty cells, but it cannot hit furniture or slide out of the ballroom; otherwise, both the piano and the furniture would be damaged, and the captain would be upset. At each moment, the piano slides one cell to an adjacent cell in the direction of the ship’s tilt. The adjacent cell can be east, west, south, or north. Emily can choose to cast magic or not: if she does not cast magic, the piano slides; if she does, the piano stays where it is.

Emily is an angel, and she knows the ship’s tilt over each time interval. She wants to make the piano travel as long a distance as possible in the ballroom, which will make 1900 very happy and also help Tooney’s seasickness. But Emily is still too young to calculate it, so she hopes you can help her.

Input Format

The first line contains 5 numbers $N$, $M$, $x$, $y$ and $K$. $N$ and $M$ describe the size of the ballroom, and $x$ and $y$ are the initial position of the piano. We describe the ship’s tilt by time intervals, and time starts from $1$. For example: “tilting east during $[1, 3]$, and tilting north during $[4, 5]$”. Therefore, $K$ is the number of intervals.

The next $N$ lines, each with $M$ characters, describe the furniture in the ballroom. In row $i$, column $j$, if the character is . then that cell is empty; if it is x then there is furniture.

The next $K$ lines describe the $K$ time intervals in order, in the format: $s_i\ t_i\ d_i$ ($1 \leq i \leq K$). It means that during the time interval $[s_i, t_i]$, the ship tilts toward direction $d_i$. $d_i$ is one of $1$, $2$, $3$, $4$, which denote north, south, west, and east respectively (corresponding to up, down, left, and right in the grid). The input guarantees that the intervals are continuous, that is, $s_1 = 1$, $s_i = t_{i-1} + 1$ ($1 < i \leq K$), $t_K = T$.

Output Format

Output a single line containing one integer, the maximum sliding distance of the piano (i.e., the number of cells).

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

6

Hint

The piano’s sliding path:

When the piano is at the "×" position, the angel uses magic once, so the total sliding length is $6$.

Constraints:

• For $50\%$ of the testdata, $1 \leq N, M \leq 200$, $T \leq 200$.
• For $100\%$ of the testdata, $1 \leq N, M \leq 200$, $K \leq 200$, $T \leq 40000$.

Translated by ChatGPT 5