# Generalized chess knight P22796

Statement

thehtml

Let us define an (a, b) knight as a piece that moves by jumping a cells in one direction and b ‍cells in the other direction, where the possible directions are horizontal and vertical. For instance, the traditional chess knight is a (1, 2) knight.

Given an n × m board with obstacles, an initial position (i1, j1), a final position (i2, j2), and the pair (a, b), can you tell if an (a, b) knight initially located at (i1, j1) can reach (i2, j2) in two or less steps? The knight can never leave the board, nor visit any obstacles.

Input

Input consists of several cases, each with n and m, followed by the board (n lines with m ‍characters each, where an ‘X’ indicates an obstacle and a ‘.’ indicates a free cell), followed by i1, j1, i2, j2, a and b. Assume that n and m are between 1 and 42, that (i1, j1) and (i2, j2) are free positions inside the board, and 1 ≤ a < b ≤ 5. The upper-left position is (0, 0).

Output

For every case, print “yes” or “no” depending on whether the goal position is reachable from the initial position in two or less steps.

Public test cases
• Input

```2 3
...
...
0 0  1 2  1 2

4 5
.....
XXXXX
XXXXX
.....
0 1  3 0  1 3

5 5
.XXX.
XXXXX
XXXXX
XXXXX
XX.XX
0 4  0 0  2 4

5 5
.XXX.
XXXXX
XXXXX
XXXXX
XXXXX
0 4  0 0  2 4

1 8
XXXXXXX.
0 7  0 7  3 5
```

Output

```yes
yes
yes
no
yes
```
• Information
Author
Enric Cusell
Language
English
Other languages
Spanish
Official solutions
C++
User solutions
C++