Description

Harry has excellent eyesight: he can look in a straight line from one side of the maze to the other (but only in eight directions — NE, E, SE, S, SW, W, NW, N). He also runs very fast: taking one step (moving one cell up, down, left, or right) costs only $1\text{s}$. However, the maze walls are opaque, and burning them down is not easy, so Harry decides to run to a place where he can see the trophy. Now he wants you to determine the minimum time needed for him to obtain the trophy.

Input Format

The first line contains $2$ numbers $N, M$ indicating the size of the maze ($N$ is height, $M$ is width).

Next comes the $N \times M$ maze: $\texttt{O}$ denotes open ground, and $\texttt{X}$ denotes a wall.

Finally, there are multiple pairs of data, each giving the coordinates of the trophy and Harry (obviously not on walls), one pair per line. A single $0$ marks the end.

Output Format

For each pair of data, output the minimum time for Harry to obtain the trophy, one per line. If the Ministry of Magic makes things difficult by surrounding the trophy with walls, output $\texttt{Poor Harry}$.

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

1
Poor Harry

Hint

For $30\%$ of the testdata, $N \times M \le 100$.

For $60\%$ of the testdata, $N \times M \le 1600$.

For $100\%$ of the testdata, $N \times M \le 16384$.

The number of query pairs does not exceed $512$.

Translated by ChatGPT 5