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