Toy

This problem is adapted from CEOI 2024 Day2 T1 "Toy".

Ben, one of the task setters for CEOI 2024, received a gift from the scientific committee—a toy. The toy is a puzzle which can be imagined as an \(H\) \(\times\) \(W\) grid containing obstacles, on which a metal object is placed. The metal object consists of two parts that are loosely connected: a horizontal bar of size \(1 \times K\) and a vertical bar of size \(L \times 1\). The bars cannot be rotated but can slide either horizontally or vertically inside the grid as long as they always share at least one common grid cell.

In the grid, there are some obstacles. No part of the metal object may pass through an obstacle, and in addition the object may not (even partially) leave the grid. Ben’s task is to move the metal object from a given starting position to a (possibly different) target position so that the two parts overlap in a specified target cell.

Your task is to determine whether it is possible to achieve the goal.

Note: A configuration of the toy is defined by a cell \((r,c)\) which is covered by both parts. For the configuration to be valid, there must exist a contiguous horizontal segment of length \(K\) in row \(r\) that contains \(c\), and a contiguous vertical segment of length \(L\) in column \(c\) that contains \(r\). Both segments must lie completely within the grid and must not contain any obstacles.

The allowed move is to slide one of the two parts by one unit in one of the four cardinal directions (up, down, left or right) while the other stays fixed, with the condition that after the move the configuration remains valid.

The puzzle is solved if there is a sequence of valid moves that brings the toy from the initial overlapping cell to the target overlapping cell.

inputFormat

The first line contains four integers \(H\), \(W\), \(K\), and \(L\) \((1 \le H,W \le 1000)\) — the grid dimensions and the sizes of the horizontal and vertical parts, respectively.

The second line contains two integers \(s_r\) and \(s_c\) \((1 \leq s_r \leq H,\ 1 \leq s_c \leq W)\) representing the initial overlapping cell of the two parts.

The third line contains two integers \(t_r\) and \(t_c\) \((1 \leq t_r \leq H,\ 1 \leq t_c \leq W)\) representing the target overlapping cell.

The following \(H\) lines each contain a string of length \(W\). Each character is either a dot ('.') denoting a free cell or a hash ('#') denoting an obstacle.

outputFormat

Output a single line containing YES if it is possible to move the toy from the starting configuration to the target configuration; otherwise, output NO.

sample

5 7 3 2
2 4
4 6
.......
..#....
.......
.##....
.......

YES