Задачи очного тура личного первенства

Шарик бросается в дырку в верхней крышке коробки, представляющей из себя лабиринт. Коробку можно наклонять в 4 направлениях N, W, S и E (как показано на рисунке, буква указывает опускаемую сторону прямоугольной коробки) и управлять таким образом движением шарика. В нижней крышке коробки есть другая дырка, через которую шарик вывалится, если он до нее докатится. Крышки и стенки коробки непрозрачны, поэтому точное местоположение шарика в коробке неизвестно. По этой причине изменять направление движения шарика можно только, когда он докатится до какой-нибудь стенки (препятствия) и остановится. Путем просвечивания коробки рентгеном было выяснено расположение стенок в лабиринте.

Напишите программу, которая определит последовательность наклонов коробки, позволяющую выкатить шарик из лабиринта.

Во входном файле в первой строке содержатся два целых числа `N` и `M`, разделенных пробелом – размеры коробки (`2\ ≤\ N\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100`). Во следующих `N` строках содержится по `M` символов. Символ '#' используется для обозначения стенки (препятствия). Символ '.' (точка) обозначает свободное место. Символ '@' обозначает вход, а символ '$' – выход. Внешние стенки коробки во входном файле не описываются.

В выходной файл вывести последовательность, позволяющую выкатить шарик из лабиринта, обозначая наклоны символами N, S, W, E (соответствие показано на рисунке). Если существует несколько вариантов вывести любой (один) из них. Если вывести шарик из лабиринта невозможно, то программа должна напечатать слово IMPOSSIBLE.

4 4
@#.$
....
.#..
...#

SENE