Рабочее место участника

Планета Топлер "прославилась" своими болотами. Многолетние наблюдения за жизнедеятельностью болот выявили следующие закономерности. Болото можно разбить на небольшие квадратные участки-клетки. Каждые 4 секунды в каждой клетке возникает большой пузырь-площадка, который постепенно в течении 3 секунд уменьшается, пока не исчезнет совсем. В течении 1 секунды клетка остается пустой, затем снова появляется пузырь, и цикл повторяется (возможно такое странное поведение пузырей объясняется обратным направлением вектора времени на планете Топлер). В течении первых 2,5 секунд существования пузырь может выдержать довольно большой вес (например, вес робота).

Для исследований планеты был изготовлен специальный прыгающий робот (на двух ножках и с длинным носом для равновесия). Робот может совершать прыжки в четыре стороны на соседние пузыри. Будем считать, что подготовка к прыжку занимает полсекунды, и на приземление после прыжка тратится полсекунды, а сам прыжок совершается мгновенно (робот не должен прыгать в клетку, которая в момент прыжка пуста, а также в клетку с пузырем, которому осталось существовать 1 секунду, если мы не хотим утопить робота в болоте). Для управления роботом используются команды: N – прыжок на север, S – на юг, W – на запад, E – на восток и D – остановка на 1 секунду.

Имеется снимок болота размером `N\ times\ M` клеток. Требуется составить программу для перехода робота через болото из юго-западного угла в северо-восточный.

Во входном файле в первой строке содержатся два целых числа `N` (`1\ <\ N\ ≤\ 50`) и `M` (`1\ <\ M\ ≤\ 50`) через один пробел – размеры болота в клетках. Далее идет `N` строк по `M` целых чисел через один пробел в каждой строке – состояние пузырей в клетках болота (клетки перечисляются с запада на восток и с севера на юг). Число 0 означает, что клетка в данный момент пуста и останется пустой в течении секунды, число от 1 до 3 означает оставшееся время существования пузыря в секундах (или его размер). Размер пузыря в юго-западном углу болота равен 3 (мы же не хотим утопить робота в первую же секунду!).

В выходной файл вывести программу управления роботом, которая позволяет достичь северо-восточного угла за минимальное время. Последовательность команд должна быть выведена как одна строка без пробелов. Если возможно несколько вариантов, то вывести любой из них. Если переход невозможен, вывести слово "IMPOSSIBLE" (кавычки не выводить).

3 4
3 2 3 3
0 0 1 2
3 3 1 2

ENEEN