Ваня рисует прямоугольник и разбивает его на M строк и N столбцов. Он заполняют некоторые ячейки монетками "Х". Две разные пустые ячейки заполняет человечком "Y" и сундуком "В". Человечек может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также человек может передвигать сундук для этого нужно встать в соседнюю к сундуку ячейку и толкнуть его от себя (сходит на ячейку к сундуку). При этом сундук передвинется на одну соседнюю ячейку в направлении, заданном толчком, а человечек переместится в ячейку, где только что находился клад. Все объекты должны быть внутри прямоугольника. В прямоугольнике могут остаться пустые ячейка ".". Задача человечка вытолкнуть клад из прямоугольника, выход из прямоугольника Ваня обозначает буквой "Т". Необходимо написать программу, которая определяет последовательность толчков и передвижений человечка, следуя которой сундук можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжелый, количество толчков должно быть минимальным. При наличии нескольких оптимальных последовательностей следует указать любую из них. Пример прямоугольника

. . Y

. B .

T X X

Формат входных данных

Первая строка содержит числа M и N . Следующие M строк содержат описание лабиринта. Каждая строка состоит из N символов, описывающих ячейки лабиринта: заполненная монетками ячейка обозначается латинской буквой "X", пустая ячейка обозначается символом "." (ASCII код 46), начальная позиция человечка — буквой "Y", начальная позиция сундука — латинской буквой "В", выход — латинской буквой "Т".

Формат выходных данных

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

Пример ввода/вывода

Ввод Вывод

3 3 YES

..Y sWnwS

.B.

TXX

vika2499    1   24.01.2022 06:30    11