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

Вхідні дані

Перший рядок містить два натуральних числа m і n - розміри лабіринту в ярдах. Наступні m рядків по n символів містять схему лабіринту, в якій символ " " (пропуск) означає вільний квадрат поверхні, символ "U" - квадрат з кущем, хрестик (знак додавання) "+" — початкове розташування Гарріса. Виходу з лабіринту відповідають елементи 1-го та m-го рядка і 1-ий та n-ий елемент кожного рядка, якщо вони є пропуском або знаком додавання. Рух у лабіринті здійснюють у напрямку сторін світу на вільний від кущів сусідній квадрат. Рухові на північ південь, захід чи схід відповідає рух вгору, вниз, ліворуч чи праворуч на один символ на вхідній схемі.

Вихідні дані

Перший рядок має містити ціле число - найменшу кількість кроків довжиною 1 ярд, які має зробити Гарріс, щоб вийти з лабіринту.

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

Якщо Гарріс вже знаходяться на виході, то перший рядок містить лише число 0, а другий рядок порожній.

Якщо вийти з лабіринту неможливо (не будемо обговорювати, яким чином у цьому випадку Гарріс потрапив у відповідне місце лабіринту), то єдиний рядок має містити лише число -1.