The Hare

The hare Bajtek lives on a rectangular meadow measuring $n \times m$ meters. The meadow is divided into $n \cdot m$ cells, each a square with side length $1$ meter. Some cells contain molehills, which Bajtek always avoids.

Each of Bajtek's jumps has length exactly $\sqrt{5}$, and because Bajtek is a terrible perfectionist he always wants to land exactly in the center of a cell. Therefore, from the cell at coordinates $(x, y)$ Bajtek can jump only to the cells at coordinates $(x+1, y+2)$, $(x+1, y-2)$, $(x-1, y+2)$, $(x-1, y-2)$, $(x+2, y+1)$, $(x+2, y-1)$, $(x-2, y+1)$, or $(x-2, y-1)$, provided the jump does not take him outside the meadow.

Bajtek would like to reach his burrow as quickly as possible without jumping onto any cell that contains a molehill. Given the cell where Bajtek is standing and the cell where his burrow is located, help him compute the minimum number of jumps he must make to reach the burrow.

The first line of standard input contains two integers $n$ and $m$ separated by a single space ($1 \le n, m \le 1000$, $n \cdot m \ge 2$), denoting the dimensions of the meadow. Each of the next $n$ lines contains $m$ characters describing the cells of the meadow:

• "." denotes a free cell, that is, a cell onto which Bajtek may jump,
• "x" denotes a cell that contains a molehill,
• "z" denotes the cell on which the hare Bajtek is currently standing,
• "n" denotes the cell that contains Bajtek's burrow.

You may assume that exactly one cell is marked "z" and exactly one cell is marked "n".

In the first and only line of standard output, print a single positive integer equal to the minimum number of jumps Bajtek must make to reach his burrow, or the word "NIE" if it is impossible for Bajtek to reach the burrow using valid jumps.