Грузчик работает на складе, который представляет собой прямоугольное поле размера n × m. Некоторые клетки этого поля свободны, остальные заняты колоннами, на которых держится крыша склада.
В одной из свободных клеток находится груз, а в другой — грузчик. Ни в какой момент времени груз и грузчик не могут находиться в клетках, занятых колоннами, за пределами склада или в одной клетке.
Грузчик может перемещаться в соседнюю клетку (две клетки считаются соседними, если у них есть общая сторона), а также двигать груз. Для передвижения груза грузчик должен встать в соседнюю с грузом клетку и толкнуть его. При этом груз переместиться в соседнюю клетку в том направлении, в котором грузчик его толкнет, а грузчик переместится в клетку, в которой находился груз.
Перед вами стоит задача определить последовательность толчков и перемещений грузчика, выполнив которые грузчик переместит груз в заданную клетку (гарантируется, что эта клетка свободна). Так как груз достаточно тяжелый, вам нужно минимизировать в первую очередь количество толчков груза, а во вторую очередь количество перемещений грузчика.
Выходные данные
Если грузчик не сможет переместить груз в заданную клетку, выведите в первую строку выходных данных «NO» (без кавычек).
В противном случае, выведите в первую строку выходных данных «YES» (без кавычек), а во вторую — последовательность символов, определяющую перемещения и толчки грузчика. Символы w, e, n, s должны обозначать перемещения грузчика на запад, восток, север и юг соответственно. Символы W, E, N, S должны обозначать толчки грузчика в соответствующих направлениях. В первую очередь вам нужно минимизировать количество толчков груза, а во вторую очередь количество перемещений грузчика. Если решений несколько, то разрешается вывести любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
..Y
.BX
..T
|
YES
wSwsE
|
|
2
|
3 3
.BY
...
TXX
|
NO
|