Карта світу в комп'ютерній грі "Цивілізація" версії 1 є прямокутником, розбитим на квадратики. Кожен квадратик може мати один із кількох можливих рельєфів, для простоти обмежимося трьома видами рельєфів – поле, ліс та вода. Поселенець переміщається картою, при цьому на переміщення у клітину, зайняту полем, необхідна одна одиниця часу, на переміщення у ліс - дві одиниці часу, а переміщатися у клітину з водою не можна.

У вас є один поселенець, ви визначили місце, де потрібно побудувати місто, щоб якнайшвидше заволодіти всім світом. Знайдіть маршрут переселенця, що приводить його до місця будівництва міста, що потребує мінімального часу. На кожному ході переселенець може переміщатися в клітину, що має спільну сторону з клітиною, де він зараз знаходиться.

Формат вхідних даних

У вхідному потоці записані два натуральні числа \(N\) і \(M\), що не перевищують 1000 - розміри карти світу (\(N\) - число рядків у карті, \(M\) - число стовпців). Потім задані координати початкового положення поселенця \(x\) і \(y\), де \(x\) - номер рядка, \(y\) - номер стовпця на карті (\(1 ≤ x ≤ N\), \(1 ≤ y ≤ M\)), рядки нумеруються зверху вниз, стовпці - зліва направо.

Потім аналогічно задаються координати клітини, куди потрібно привести поселенця.

Далі йде опис карти світу у вигляді \(N\) рядків, кожен з яких містить \(M\) символів. Кожен символ може бути або "." (точка), що означає поле, або “W”, що означає ліс, або “#”, що означає воду. Гарантується, що початкова та кінцева клітини шляху переселенця не є водою.

Формат вихідних даних

У першому рядку виведіть кількість одиниць часу, необхідну для переміщення поселенця (переміщення в клітину з полем займає 1 одиницю часу, переміщення в клітину з лісом - 2 одиниці часу). У другому рядку вихідного файлу виведіть послідовність символів, які задають маршрут переселенця. Кожен символ має бути одним із чотирьох наступних: “N” (рух вгору), “E” (рух праворуч), “S” (рух вниз), “W” (рух вліво). Якщо таких маршрутів є кілька, виведіть будь-який з них. Якщо дійти з початкової клітини до кінцевої неможливо, виведіть число -1.

Приклад вхідних даних

4 8 1 1 4 8
....WWWW
.######.
.#..W...
...WWWW.

Приклад вихідних даних

13
SSSEENEEEEES

Приклад вхідних даних

4 7 2 2 3 6
#######
#WW#..#
#WW#..#
#######

Приклад вихідних даних

-1