Horse Jumping

Interview

Time limit6sMemory limit1024 MB

Summary

Two horses on a grid move like chess knights and cannot land on stones. Determine whether their reachable cells overlap.

Level: Easy3 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

Hsara and Pascal, two fast horses, live together in a two-dimensional pasture with $N$ rows and $M$ columns. The pasture is surrounded by a large fence, and inside it are cells where the horses can jump freely. Both horses want to avoid landing on cells that contain large stones.

A jump follows the chess knight pattern: two steps in one direction and then one step in a direction perpendicular to the first. A horse may jump over stones, but the cell where it lands must be free. Given the layout of the pasture and the starting positions of the horses, determine whether they can meet. They can meet if there is a sequence of jumps that brings both horses to the same cell.

Input

The first line contains the integers $N$ and $M$ , separated by a space.

The next $N$ lines each contain $M$ characters describing the cells of the pasture. A '.' is an empty cell, '\#' is a cell with a stone, and 'H' is a cell where one of the horses stands.

The pasture is surrounded by a fence. The input is guaranteed to contain exactly two 'H' cells.

Output

Print one word on a line: "JA" if the horses can meet on some cell, and "NEJ" otherwise.

Constraints

$3 \le N, M \le 500$

Hint

The illustration shows Sample Input 2 and how Pascal can jump to reach Hsara.

Examples3

Example 1
Input
```
2 2
H.
.H
```
Expected output
```
NEJ
```
Example 2
Input
```
3 3
H.H
...
.#.
```
Expected output
```
JA
```
Example 3
Input
```
3 3
H#H
...
.#.
```
Expected output
```
NEJ
```