Создайте программу, которая поможет герою произведения Джерома К.Джерома "Трое в лодке, не считая собаки" Гарри быстрее выйти из Хэмптон-Кортского лабиринта. Лабиринт на плане имеет вид прямоугольника, стороны которого направлены с запада на восток или с севера на юг (насколько это возможно, учитывая шарообразную форму Земли). Размеры лабиринта в ярдах (англ мера длины, примерно 91,44 см) вдоль параллели и меридиана выражено натуральными числами n и m соответственно, а его общая площадь m * n не превышает 10000 (квадратных ярдов). Всю территорию лабиринта разделен на квадраты с длиной стороны 1 ярд. Часть квадратов засажено кустами с колючками, которые можно только обойти.

Входные данные

Первая строка содержит два натуральных числа m и n - размеры лабиринта в ярдах. Следующие m строк по n символов содержат схему лабиринта, в которой символ " " (пробел) означает свободный квадрат поверхности, символ "U" - квадрат с кустом, крестик (знак сложения) "+" - начальное расположение Харриса. Выходу из лабиринта соответствуют элементы 1-ой и m-ой строки и 1-ого и n-ого столбца, если они являются пропуском или знаком сложения. Движение в лабиринте осуществляют в направлении сторон света на свободный от кустов соседний квадрат. Движению на север юг, запад или восток соответствует движение вверх, вниз, влево или вправо на один символ на входной схеме.

Выходные данные

Первая строка должна содержать наименьшее количество шагов длины 1 ярд, которые должен совершить Гарри чтобы выйти из лабиринта.

Вторая строка должна содержать описание такого кратчайшего пути - шагов от первого до последнего, в котором буква n обозначает шаг на север (по-английски north), s - на юг (south), e - на восток (east), w - на запад (west).

Если Гарри уже находится на выходе, то первая строка содержит только число 0, а вторая строка пустая.

Если выйти из лабиринта невозможно (не будем обсуждать каким образом в этом случае Гарри попал в соответствующее место лабиринта), то единственная строка должна содержать только число -1.