Монокарп играет в Minecraft и хочет построить стену из кактусов. Он хочет построить ее на поле из песка размера \(n \times m\) клеток. Изначально в некоторых ячейках поля есть кактусы. Обратите внимание, что в Minecraft кактусы не могут расти на соседних по стороне клетках; и начальное поле соответствует этому ограничению. Монокарп может сажать новые кактусы (они также должны соответствовать вышеупомянутому условию). Он не может срубить ни один из кактусов, которые уже растут на поле — у него нет топора, а кактусы слишком колючие для его рук.
Монокарп считает, что стена завершена, если нет пути от верхнего ряда поля к нижнему ряду, такого, что:
- каждые две последовательные клетки в пути соседние по стороне;
- ни одна ячейка, принадлежащая пути, не содержит кактуса.
Ваша задача — посадить минимальное количество кактусов, чтобы построить стену (или сообщить, что это невозможно).
Выходные данные
Для каждого набора входных данных, в первой строку выведите NO, если невозможно построить стену кактусов не нарушая правил. В противном случае в первой строке выведите YES, затем выведите \(n\) строк по \(m\) символов — поле с кактусами, где \(j\)-й символ \(i\)-й строки равен '#', если на если на пересечении \(i\)-й строки и \(j\)-го столбца поля есть кактус, в противном случае символ равен '.'. Если существует несколько оптимальных решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...
|
YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...
|