Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

I. Грузчик
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Грузчик работает на складе, который представляет собой прямоугольное поле размера n × m. Некоторые клетки этого поля свободны, остальные заняты колоннами, на которых держится крыша склада.

В одной из свободных клеток находится груз, а в другой — грузчик. Ни в какой момент времени груз и грузчик не могут находиться в клетках, занятых колоннами, за пределами склада или в одной клетке.

Грузчик может перемещаться в соседнюю клетку (две клетки считаются соседними, если у них есть общая сторона), а также двигать груз. Для передвижения груза грузчик должен встать в соседнюю с грузом клетку и толкнуть его. При этом груз переместиться в соседнюю клетку в том направлении, в котором грузчик его толкнет, а грузчик переместится в клетку, в которой находился груз.

Перед вами стоит задача определить последовательность толчков и перемещений грузчика, выполнив которые грузчик переместит груз в заданную клетку (гарантируется, что эта клетка свободна). Так как груз достаточно тяжелый, вам нужно минимизировать в первую очередь количество толчков груза, а во вторую очередь количество перемещений грузчика.

Входные данные

В первой строке входных данных следует два целых положительных числа n и m (1 ≤ n, m ≤ 40, n·m ≥ 3) — количество строк и количество столбцов в прямоугольном поле.

В следующих n строках следует по m символов — описание склада. Если в очередной клетке склада находится символ

  • «X», это означает, что в текущей клетке находится колонна;
  • «.», это означает, что текущая клетка свободна;
  • «Y», это означает, что в текущей клетке находится грузчик;
  • «B», это означает, что в текущей клетке находится груз;
  • «T», это означает, что груз нужно переместить в эту клетку.

Гарантируется, что на складе есть ровно один груз, ровно один грузчик и ровно одна клетка, в которую нужно переместить груз.

Выходные данные

Если грузчик не сможет переместить груз в заданную клетку, выведите в первую строку выходных данных «NO» (без кавычек).

В противном случае, выведите в первую строку выходных данных «YES» (без кавычек), а во вторую — последовательность символов, определяющую перемещения и толчки грузчика. Символы w, e, n, s должны обозначать перемещения грузчика на запад, восток, север и юг соответственно. Символы W, E, N, S должны обозначать толчки грузчика в соответствующих направлениях. В первую очередь вам нужно минимизировать количество толчков груза, а во вторую очередь количество перемещений грузчика. Если решений несколько, то разрешается вывести любое из них.

Примеры
Входные данные
3 3
..Y
.BX
..T
Выходные данные
YES
wSwsE
Входные данные
3 3
.BY
...
TXX
Выходные данные
NO