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

Вам дана таблица $$$n \times m$$$. Некоторые клетки заполнены, некоторые пустые.

Город — это максимальное (по включению) множество заполненных клеток, такое что можно дойти из любой клетки города до любой другой клетки города, перемещаясь в соседние по стороне клетки, только по клеткам города. Другими словами, город — это компонента связности заполненных клеток, где ребро проводится между соседними по стороне заполненными клетками.

Изначально в таблице находятся два города. Вы хотите поменять некоторые пустые клетки на заполненные, так что выполняются два условия:

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

Манхеттенское расстояние между двумя клетками $$$(a, b)$$$ и $$$(c, d)$$$ равняется $$$|a - c| + |b - d|$$$.

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

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Описания наборов входных данных следуют.

В первой строке описания каждого набора входных данных находится два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 50$$$, $$$nm \geq 3$$$).

Следующие $$$n$$$ строк описывают таблицу. В $$$i$$$-й строке находится строка $$$s_i$$$ длины $$$m$$$. Символ $$$s_{i,j}$$$ равен '#', если клетка $$$(i, j)$$$ заполнена, и '.', если клетка пустая.

Гарантируется, что изначально в таблице ровно два города.

Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превосходит $$$25\,000$$$.

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

Для каждого набора входных данных выведите $$$n$$$ строк, каждая содержит строку длины $$$m$$$ — описание таблицы, которую вы сделали в том же формате, что во входных данных.

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

Пример
Входные данные
11
1 3
#.#
2 2
.#
#.
4 4
..##
...#
#...
##..
6 6
.##...
##....
......
....##
.....#
...###
6 5
.#..#
.#..#
.#..#
.#.##
.#...
##...
5 5
#####
#...#
#.#.#
#...#
#####
4 4
.##.
##.#
#.##
.##.
5 5
..###
....#
.....
#....
#....
5 6
.##...
##....
#....#
....##
...##.
6 5
..##.
...##
....#
#....
##...
.##..
5 4
..##
..#.
..#.
#...
#...
Выходные данные
###

.#
##

..##
..##
###.
##..

.##...
###...
..#...
..####
...###
...###

.####
.####
.####
.####
.#...
##...

#####
#####
#####
#####
#####

.##.
####
####
.##.

..###
..###
..#..
###..
#....

.##...
###...
######
...###
...##.

..##.
..###
..###
###..
###..
.##..

..##
..#.
..#.
###.
#...
Примечание

В первом наборе входных данных мы добавляем одну заполненную клетку между двумя городами, чтобы соединить их. Можно убедиться, что второе условие также выполняется.

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

В третьем наборе входных данных, обратите внимание, что если мы заполним 3 клетки слева сверху, города будут соединены, однако второе условие не будет выполняться для пары клеток $$$(4, 2)$$$ и $$$(2, 4)$$$.