Problem description

W ramach programu eksploracji kosmosu, NASA zdecydowała się wysłać doktora Bitstronga, wraz z jego ekipą wytresowanych małp w skafandrach, na specjalną misję na nieznanej planecie. Niestety, pech chciał, że planeta ta nie dość, że jest pełna niebezpieczeństw, to jeszcze rosną na niej kosmiczne banany!

Wystarczyła tylko chwila nieuwagi, a cała małpia załoga rozproszyła się po okolicy w poszukiwaniu jedzenia i całkowicie zniknęła z pola widzenia doktora. Bitstrong chciałby sprowadzić zwierzęta z powrotem, więc poprosił centralę o udostępnienie zdjęć satelitarnych obszarów z małpami, aby móc poprawnie pokierować towarzyszy z powrotem do siebie.

Centrala NASA przesłała mu sześć zdjęć satelitarnych, każde przedstawiające jeden z obszarów, na którym znalazły się małpy. Ze względu na to, że komunikacja między kosmosem i Ziemią jest bardzo utrudniona, każdy obraz to tablica znaków ASCII. Niestety, do doktora nie dotarła informacja co one oznaczają, ale Bitstrong wie, że zostały one wybrane przez ekspertów tak, aby to co reprezentują było jak najbardziej intuicyjne (spokojnie, zawsze te same obiekty oznaczone są tym samym znakiem). Każdy znak przedstawia jeden metr kwadratowy powierzchni. Wiadomo też, że na wszystkich zdjęciach każdy metr kwadratowy zawiera w sobie maksymalnie jeden obiekt. No i oczywiście na każdym obszarze jest też co najmniej jedna małpa oraz punkt zbiórki.

Małpy są bardzo dobrze wytresowane i zawsze słuchają się poleceń. Trudność polega na tym, że wszystkie małpy na tym samym obszarze korzystają ze wspólnego kanału łączności, więc każde polecenie wydawane jest do wszystkich jednocześnie. Małpy znają tylko cztery bardzo proste komendy – POLNOC, POLUDNIE, ZACHOD i WSCHOD. Każda z nich, jak pewnie łatwo się domyślić, powoduje przesunięcie się małp w danym kierunku o jeden metr, o ile jest taka możliwość (jeśli małpa nie może z różnych przyczyn wykonać tego polecenia, stoi w miejscu).

Zaproponuj dla doktora ciąg komend, który pozwoli pokierować zwierzaki tak, aby każde z nich bezpiecznie dotarło do punktu zbiórki. Pamiętaj, żeby małpy zebrały po drodze wszystkie pozostałe kosmiczne banany – nie chcemy przecież, żeby znowu wszystkie się rozbiegły!

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita T, oznaczająca numer obszaru.
W drugim wierszu wejścia znajdują się dwie liczby całkowite N i M oddzielone pojedynczym odstępem, oznaczające wymiary tablicy ASCII reprezentującej mapę. W następnych N wierszach znajduje się po M znaków ASCII (bez znaków białych), symbolizujących zawartość zdjęcia satelitarnego.

Wyjście

Program powinien wypisać jedną liczbę całkowitą L nie większą niż 10 000, a następnie L wierszy, każdy zawierający jedno ze słów: POLNOC, POLUDNIE, ZACHOD albo WSCHOD. Powinny one przedstawiać poprawną listę komend, która umożliwi małpom z danego obszaru bezpieczne dotarcie do punktu zbiórki.

Ograniczenia

1 ≤ T ≤ 6, 1 ≤ N, M ≤ 15.

Obszary

Poniżej przedstawione są wszystkie obszary, które są do rozwiązania. W zadaniu nie będzie innych testów.

1
9 9
#########
#......@#
#.##.####
#.@#....#
####.##.#
#@#..#..#
#.#.##.##
#...#^.##
#########

2
9 9
#########
#@.....x#
#xxxx..x#
#@..#..x#
#^..x..x#
#..#x..x#
#......x#
#xxxxxxx#
#########

3
9 9
#########
#...)...#
#..@....#
#.......#
#.^...).#
#@......#
#..)....#
#......@#
#########

4
9 9
#########
#@.#...O#
#O)#....#
####....#
#...^...#
#...xxxx#
#...x.).#
#o.@xo..#
#########

5
9 9
#########
#@O#..xO#
#.....xx#
#...)...#
#.......#
#xxxxxx.#
#x@....^#
#xxxxxxx#
#########

6
13 15
###############
#xxxxxxx#xxxxx#
#.........@...#
#o###########^#
#x............#
#............x#
#)OO....x.x).x#
########x.x####
#).........@..#
#xxxxxxx#xxxxx#
#...).....@..o#
#xxxxxxxxxxxxx#
###############

Testowanie

Rozwiązania do pierwszych pięciu obszarów, bez kary czasowej za błędną odpowiedź, możesz testować na następującej stronie: https://mistrzostwa.solve.edu.pl/task/bananowa-przygoda/special.