Осталось несколько дней до Корейского Нового года, и Джаехьюн пригласил свою семью в сад. Среди гостей есть дети. Чтобы сделать времяпровождение для них интереснее, Джаехьюн решил устроить игру в прятки.
Сад можно описать как таблицу \(n \times m\) из единичных клеток. Некоторые (возможно ноль) из них заняты камнями, а остальные свободны. Две клетки называются соседними если у них есть общее ребро. Таким образом, у каждой клетки есть не более четырех соседей: два по горизонтали, и два по вертикали.
Так как сад можно описать как таблицу, клетки бывают двух видов: «черные» или «белые», как в шахматной доске. Первая клетка \((1, 1)\) черная. А затем, остальные клетки покрашены чередуясь. Клетки пронумерованы в 1-индексации.
Джаехьюн хочет превратить его сад в лабиринт расстановкой стен между двумя клетками. Стены могут быть размещены только между соседними клетками. Если поставить стену между двумя соседними клетками \(a\) и \(b\), тогда клетки \(a\) и \(b\) больше не считаются соседними. Можно идти прямо между двумя соседними клетками тогда и только тогда, когда нет прямой стены между ними.
Лабиринт должен обладать следующим свойством. Для каждой пары свободных клеток, должен быть ровно один простой путь между ними. Простой путь между клетками \(a\) и \(b\) это последовательность клеток, в которой первая клетка \(a\), последняя \(b\), все клетки различны, и любые две подряд идущие клетки являются соседями, между которыми не стоит стена.
Сначала, дети соберутся в клетке \((1, 1)\), и начнут играть в прятки. Ребенок может спрятаться в клетке если и только если это не стартовая клетка \((1, 1)\), и у нее есть ровно один свободный сосед. Джаехьюн посадил розы в черных клетках, так что там опасно прятаться. Поэтому Джаехьюн хочет построить лабиринт, в котором дети смогут прятаться только в клетках белого цвета.
Вам дана карта сада. Ваша задача — помочь Джаехьюну построить лабиринт.
Выходные данные
Для каждого тестового случая, выведите следующее:
Если нет возможных лабиринтов, выведите NO.
Иначе, выведите YES, после чего выведите таблицу \((2n-1) \times (2m-1)\) описывающих выбранный лабиринт. Все клетки в 1-индексации. Правила описания лабиринта следующие:
- Для всех \(1 \le i \le n, 1 \le j \le m\), если клетка \((i, j)\) свободная, выведите 'O' в клетке \((2i-1, 2j-1)\). Иначе, выедите 'X' в клетке \((2i-1, 2j-1)\).
- Для всех \(1 \le i \le n, 1 \le j \le m-1\), если между клетками \((i, j), (i, j+1)\) стоит стена, выведите ' ' в клетке \((2i-1, 2j)\). Иначе, выведите любой выводимый символ кроме пробела в клетке \((2i-1, 2j)\). У выводимого символа ASCII код расположен в отрезке \([32, 126]\): Это включает пробелы, буквы, и цифры.
- Для всех \(1 \le i \le n-1, 1 \le j \le m\), если между клетками \((i, j), (i+1, j)\) стоит стена, выведите ' ' в клетке \((2i, 2j-1)\). Иначе, выведите любой выводимый символ кроме пробела в клетке \((2i, 2j-1)\).
- Для всех \(1 \le i \le n-1, 1 \le j \le m-1\), выведите любой выводимый символ в клетке \((2i, 2j)\).
Пожалуйста, будьте аккуратны с лишними символами переноса строк и пробелами. Каждая строка таблицы должна содержать ровно \(2m-1\) символов, а строки должны быть разделены символом новой строки. Пробелы в конце строк не должны быть пропущены.