toy (CEOI contest)
Time limit: 1.35 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: graph traversal, bfs, graph theory, dynamic programming

# Toy

For creating a task for CEOI 2024,
Ben was given a toy as a present from the scientific committee.
The toy is a puzzle which can be imagined as a $H \times W$ grid
containing a metal object consisting of two parts:
A horizontal $1\times K$ part and a vertical $L \times 1$ part,
which are loosely attached to each other.
Neither of the parts can be rotated in any way,
but each can be slid vertically or horizontally independently of the other one,
as long as they always overlap on exactly one square.

Furthermore, the grid contains several obstacles.
No part of the metal object can move through an obstacle.
Worse yet, the parts also cannot move outside the grid, not even partially.
Ben's task is to move the metal object from a designated starting location
to a (possibly) different location
so that both parts overlap on a designated target square.

However, Ben has been playing with the toy for a while and
he has not yet been able to solve the task.
In fact, he has gained a suspicion that the organizers have played a prank on him
and have given him an unsolvable puzzle.
He thus asks for your help by telling him whether the puzzle is solvable or not.

## Input

The first line of the input contains four space-separated integers $W$, $H$, $K$ and $L$ —
the width and the 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$ and $y_v$ —
the coordinates of the leftmost square occupied by the horizontal part and
the coordinates of the topmost square occupied by the vertical part.

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

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

It is guaranteed that the initial position of the metal object is valid,
i.e., that the two parts overlap on exactly one square and
the two parts neither overlap with an obstacle nor stick out from the grid.

There is a single target square, i.e., a single occurrence of the `*` symbol
in the toy, which might overlap with the initial position of the metal object.

## Output

Print a single line containing `YES`
if it is possible to move the metal object to the target square,
`NO` otherwise.

## Examples

### Example 1
Input:
```
4 3 2 2
0 1 0 0
.X.*
....
...X
```
Output:
```
YES
```
The initial situation looks as follows:
![](toy-sample1-v3.svg)

We can reach the target square by first moving the vertical part one square down,
followed by alternating movement to the right of the vertical and horizontal parts as long as possible.
Then we can move the vertical part up and to the right,
reaching the target square,
and finally move the horizontal part up,
reaching the target as well.

 <div style='page-break-after: always'></div>

### Example 2
Input:
```
2 3 2 3
0 1 0 0
.X
.*
.X
```
Output:
```
NO
```

There is no way how to move the vertical part without running into an obstacle.
Therefore, it can never reach the target square.

## Constraints
- $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$

## Subtasks
1. (14 points) $W, H \le 50$
2. (21 points) $W, H \le 90$
3. (9 points)  $W, H \le 300$ and $K, L \le 10$
4. (29 points) $W, H \le 360$
5. (27 points) _no additional constraints_


Starter code:

Grader code:

Setup script:

Evaluation script: