Павел обожает клетчатые лабиринты. Клетчатый лабиринт — это прямоугольный лабиринт размера n × m, где каждая клетка либо свободна, либо является стеной, а перемещаться из одной клетки в другую можно только в том случае, если они обе свободные и имеют общую сторону.
Павел нарисовал клетчатый лабиринт, все свободные клетки которого образуют связную область, то есть из любой свободной клетки можно добраться до любой другой. Павлу не нравится, что в его лабиринте слишком мало стен. Он хочет превратить ровно k свободных клеток в стены таким образом, чтобы все оставшиеся свободные клетки по прежнему образовывали бы связную область. Помогите ему.
Выходные данные
Выведите n строк по m символов каждая: новый лабиринт, удовлетворяющий всем требованиям Павла. Пустые клетки, которые после преобразования стали стенами, обозначайте «X», а остальные клетки оставляйте без изменения (то есть «.» и «#»).
Гарантируется, что решение существует. Если существует несколько решений, разрешается вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 2
#..#
..#.
#...
|
#.X#
X.#.
#...
|
|
2
|
5 4 5
#...
#.#.
.#..
...#
.#.#
|
#XXX
#X#.
X#..
...#
.#.#
|