Problem Description

Translated from CEOI 2024 Day2 T1「Toy」

Ben, the problem setter for CEOI 2024, received a gift from the scientific committee—a toy puzzle. This puzzle can be imagined as a grid of $H$ rows and $W$ columns, with a metallic object placed on it. The metallic object consists of two parts: a horizontal part of $1$ row and $K$ columns, and a vertical part of $L$ rows and $1$ column, which are loosely connected. Neither part can be rotated, but they can slide horizontally or vertically within the grid as long as they always overlap on one square.

The grid also contains some obstacles. Neither part of the metallic object can pass through obstacles, nor can they move out of the grid, even partially. Ben's task is to move the metallic object from a specified starting position to a (possibly different) target position, such that the two parts overlap on the specified target square.

However, Ben has been playing with this toy for a while and has not solved the puzzle. In fact, he began to suspect that the organizers were teasing him with an unsolvable puzzle. Therefore, he seeks your help to determine if the puzzle is solvable.

Input Format

The first line of input contains four space-separated integers $W, H, K, L$, representing the width and height of the puzzle, the width of the horizontal part, and the height of the vertical part, respectively. The second line contains four integers $x_h, y_h, x_v, y_v$, indicating the coordinates of the top-left square of the horizontal part and the top-left square of the vertical part.

Rows are numbered from $0$ to $H-1$ from top to bottom, and columns are numbered from $0$ to $W-1$ from left to right. The $x$ coordinate represents the column number, and the $y$ coordinate represents the row number.

The next $H$ lines each contain $W$ characters, representing the grid. The character . denotes an empty square, X denotes an obstacle, and * denotes the target square.

It is guaranteed that the initial position of the metallic object is valid, meaning the two parts overlap on one square, and neither part overlaps with an obstacle nor extends beyond the grid.

There is only one target square, represented by the character *, which may overlap with the initial position of the metallic object.

Output Format

If the metallic object can be moved to the target square, output one line YES; otherwise, output NO.

Sample Input and Output

Sample Input #1

4 3 2 2
0 1 0 0
.X.*
....
...X

Sample Output #1

YES

Sample Input #2

2 3 2 3
0 1 0 0
.X
.*
.X

Sample Output #2

NO

Notes/Hints

Sample Explanation 1

The initial state is as follows:

We can first move the vertical part down by one square, then move the horizontal and vertical parts alternately as far as possible. After that, we can move the vertical part up and right to reach the target square, and finally move the horizontal part up to reach the target square as well.

Sample Explanation 2

It is impossible to move the vertical part without hitting an obstacle, so it is never possible to reach the target square.

For all input data, the following conditions are satisfied:

• $2 \leq W, H \leq 1\,500$
• $2 \leq K \leq W, 2 \leq L \leq H$
• $0 \leq x_h \leq W - K, 0 \leq y_h \leq H - 1$
• $0 \leq x_v \leq W - 1, 0 \leq y_v \leq H - L$

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分