Have you ever danced a waltz? When the music starts and you glide along with the melody, isn't there a sense of comfort as if you are strolling through a fairyland?
As everyone knows, the most important thing when dancing a waltz is good music. But few people know that the world's greatest pianist spent his entire life drifting on the ocean. His name was Danny Boodman T.D. Lemon 1900, and his friends called him 1900.
1900 was born in the first year of the 20th century on the ocean liner Virginia, which traveled between Europe and America. Unfortunately, he was abandoned at birth and became an orphan. 1900 grew up lonely on the Virginia, never leaving this swaying world. Perhaps as compensation for his fate, God sent a lovely little angel, Emily, to take care of him.
Perhaps through the angel's guidance, 1900 possessed an incredible talent for the piano: he had never been taught, had never seen a musical score, yet he could play the most heart-touching melodies based on his own feelings. When 1900's music became popular with everyone on the cruise ship, he was only 8 years old, and by then, he had already traveled back and forth across the Atlantic Ocean more than 50 times.
Although he was a piano prodigy, 1900 was still a child, with the same curiosity and playfulness as any other boy, just with an extra layer of romantic color:
It was a stormy night, with sea winds whipping up giant waves that battered the Virginia, causing the cruise ship to sway violently. The ship's new saxophonist, Max Tooney, was seasick. 1900 invited Tooney to sit with him at the piano in the ballroom, then released the brake that secured the piano, and the piano began to slide along with the tilting of the ship. To be precise, our protagonist 1900, the piano, and the cruise ship danced a waltz together to the rhythm of 1900's melody. With the "boom-cha-cha" rhythm, Tooney's seasickness miraculously disappeared. Later, Tooney wrote in his memoirs:
The ocean rocks us Makes us spin around Swiftly gliding past lights and furniture I realize we are dancing with the ocean What a perfect and crazy dancer
Isn't it pleasant to dance a waltz happily on the golden floor at night? Perhaps we have forgotten one person, and that is Emily. She was not idle: she had to cast magic at the right time to help 1900 so that the piano would not bump into the furniture in the ballroom.
We can think of the ballroom as an $N \times M$ matrix. Some squares in the matrix are piled with furniture, while others are empty spaces. The piano can slide on the empty spaces, but it cannot hit furniture or slide out of the ballroom, otherwise, the piano and furniture will be damaged, attracting the troublesome captain.
At each moment, the piano slides one square in the direction of the ship's tilt to an adjacent square. The adjacent square can be to the east, west, south, or north. Emily can choose to cast magic or not: if she does not cast magic, the piano will slide; if she casts magic, the piano will remain in place.
Emily is an angel, and she knows the ship's tilt for each time interval. She wants to make the piano's sliding distance in the ballroom as long as possible, which would make 1900 very happy and also help cure Tooney's seasickness. But Emily is still too young to calculate this, so she hopes you can help her.
Input
The first line of the input file 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 in terms of time intervals, and time is calculated starting from 1. For example, "tilting east during time $[1, 3]$, tilting north during time $[4, 5]$". Therefore, $K$ here represents the number of intervals.
The next $N$ lines, each containing $M$ characters, describe the furniture in the ballroom. If the character at the $i$-th row and $j$-th column is '.', it represents an empty space; if it is 'x', it represents furniture.
The next $K$ lines describe the $K$ time intervals in order, in the format: $s_i \ t_i \ d_i$ ($1 \le i \le K$). This indicates that during the time interval $[s_i, t_i]$, the ship is tilting in direction $d_i$. $d_i$ is one of 1, 2, 3, 4, representing north, south, west, and east respectively (corresponding to up, down, left, and right in the matrix). The input guarantees that the intervals are continuous, i.e., $s_1 = 1$ $t_i = s_{i-1} + 1$ ($1 < i \le K$) $t_K = T$
Output
The output file contains only one integer, representing the maximum distance the piano slides (i.e., the number of squares).
Examples
Input 1
4 5 4 1 3 ..xx. ..... ...x. ..... 1 3 4 4 5 1 6 7 2
Output 1
6
Note
The piano's sliding route:
When the piano is at the "x" position, the angel uses magic once, so the total sliding length is 6.
Constraints
In 50% of the data, $1 \le N, M \le 200, T \le 200$; In 100% of the data, $1 \le N, M \le 200, K \le 200, T \le 40000$.