Zając

Limit pamięci: 32 MB

Zając Bajtek mieszka na polanie w kształcie prostokąta o wymiarach metrów. Polana ta jest podzielona na pól - kwadratów o boku długości metra. Na niektórych polach znajdują się kopce kreta, które Bajtek zawsze omija.

Każdy skok Bajtka ma długość dokładnie , a ponieważ Bajtek jest strasznym pedantem - zawsze chce skoczyć dokładnie na środek pola. Tak więc z pola o współrzędnych (, ) Bajtek może skoczyć tylko na pola o współrzędnych: , , , , , , lub , o ile nie wiąże się to z wyskoczeniem poza polanę.

Bajtek chciałby jak najszybciej dotrzeć do swojej nory, nie skacząc na pola, na których znajdują się kopce kreta. Mając dane pole, na którym stoi Bajtek, oraz pole, na którym znajduje się jego nora, pomóż mu obliczyć minimalną liczbę skoków, jakie musi wykonać, aby dotrzeć do nory.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz oddzielone pojedynczym odstępem (, ), oznaczające rozmiary polany. Kolejne wierszy zawiera po znaków oznaczających poszczególne pola polany:

• "." oznacza wolne pole, czyli takie, na które Bajtek może wskoczyć,
• "x" oznacza pole, na którym znajduje się kopiec kreta,
• "z" oznacza pole, na którym obecnie stoi zając Bajtek,
• "n" oznacza, że na tym polu jest nora Bajtka.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna dodatnia liczba całkowita równa minimalnej liczbie skoków, jakie Bajtek musi wykonać, aby dotrzeć do swojej nory, lub słowo "NIE", jeśli dotarcie Bajtka do nory przy użyciu poprawnych skoków nie jest możliwe.

Przykład

Dla danych wejściowych:

4 5
.zx.x
.xx..
..x.x
x..n.

poprawną odpowiedzią jest:

3

Autor zadania: Oskar Wantoła.