Цивілізація
Карта світу у комп'ютерній грі “Цивілізація” версії 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.