A. Защитить овец
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб — пастух. Он пасет своих овец на большом пастбище. Недавно волки утащили нескольких из его овец. Поэтому он решил обзавестись несколькими собаками-пастухами, которые будут защищать всех его овец.

Пастбище можно представить как прямоугольник из R × C клеток. Каждая клетка либо пустая, либо содержит овцу, волка или собаку. Овцы и собаки не могут двигаться, однако волки могут перемещаться по пастбищу свободно, каждый раз перемещаясь влево, вправо, вверх или вниз в соседнюю клетку. Если волк доберется до клетки с овцой, он съест ее. Однако волк не может зайти в клетку, где находится собака.

Изначально собак нет. Расположите собак на пастбище так, чтобы никакой волк не мог бы добраться до никакой овцы, или определите, что это невозможно. Обратите внимание на то, что у вас достаточно собак, поэтому вам не нужно минимизировать их количество.

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

Первая строка содержит два целых числа R (1 ≤ R ≤ 500) и C (1 ≤ C ≤ 500) — число строк и число столбцов на пастбище, соответственно.

Каждая из следующих R строк содержит строку, состоящую из ровно C символов и описывающую одну строку пастбища. Здесь «S» означает клетку с овцой, «W» означает клетку с волком, а «.» означает пустую клетку.

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

Если невозможно защитить всех овец, выведите одну строчку со словом «No».

Иначе выведите одну строку со словом «Yes». Затем выведите R строк, описывающих пастбище после того, как вы расставили собак. Как и во входных файлах, «S» означает клетку с овцой, «W» означает клетку с волком, «D» — собаку, а «.» — пустую клетку. Вы не можете перемещать, добавлять или удалять волков или овец.

Если существует несколько решений, выведите любое из них. Вам не обязательно минимизировать число собак.

Примеры
Входные данные
6 6
..S...
..S.W.
.S....
..W...
...W..
......
Выходные данные
Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......
Входные данные
1 2
SW
Выходные данные
No
Входные данные
5 5
.S...
...S.
S....
...S.
.S...
Выходные данные
Yes
.S...
...S.
S.D..
...S.
.S...
Примечание

В первом примере можно разбить пастбище собаками на две половины, в одной из которых находятся овцы, а в другой — волки. Обратите внимание на то, что овца в клетке (2,1) находится в безопасности, так как волки не могут двигаться по диагонали.

Во втором примере нет мест, куда можно было бы добавить собаку для защиты единственной овцы.

В третьем примере нет волков, поэтому задача очень проста. Мы посадили одну собаку в центр, чтобы она олицетворяла собой безопасность, однако решение без нее тоже верно.