E. Кактусовая стена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в Minecraft и хочет построить стену из кактусов. Он хочет построить ее на поле из песка размера $$$n \times m$$$ клеток. Изначально в некоторых ячейках поля есть кактусы. Обратите внимание, что в Minecraft кактусы не могут расти на соседних по стороне клетках; и начальное поле соответствует этому ограничению. Монокарп может сажать новые кактусы (они также должны соответствовать вышеупомянутому условию). Он не может срубить ни один из кактусов, которые уже растут на поле — у него нет топора, а кактусы слишком колючие для его рук.

Монокарп считает, что стена завершена, если нет пути от верхнего ряда поля к нижнему ряду, такого, что:

  • каждые две последовательные клетки в пути соседние по стороне;
  • ни одна ячейка, принадлежащая пути, не содержит кактуса.

Ваша задача — посадить минимальное количество кактусов, чтобы построить стену (или сообщить, что это невозможно).

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$; $$$n \times m \le 4 \cdot 10^5$$$) — количество строк и столбцов, соответственно.

Затем следуют $$$n$$$ строк, $$$i$$$-я строка содержит строку $$$s_i$$$ длины $$$m$$$, где $$$s_{i, j}$$$ равно '#', если на пересечении $$$i$$$-й строки и $$$j$$$-го столбца растет кактус, и $$$s_{i, j}$$$ равно '.' в противном случае.

Сумма $$$n \times m$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$.

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

Для каждого набора входных данных, в первой строку выведите NO, если невозможно построить стену кактусов не нарушая правил. В противном случае в первой строке выведите YES, затем выведите $$$n$$$ строк по $$$m$$$ символов — поле с кактусами, где $$$j$$$-й символ $$$i$$$-й строки равен '#', если на если на пересечении $$$i$$$-й строки и $$$j$$$-го столбца поля есть кактус, в противном случае символ равен '.'. Если существует несколько оптимальных решений, выведите любое из них.

Пример
Входные данные
4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...
Выходные данные
YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...