Рабочее место участника

Несколько участков земли были выделены в Сколково для строительства фабрики по производству микросхем. По периметру участков должен быть построен забор. Для уменьшения стоимости строительства было решено заменить некоторые участки на аналогичные по площади так, чтобы суммарная площадь участков для строительства осталась прежней, а периметр области, объединяющей выбранные участки, имел минимальную длину.

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

Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 20`). Каждая из следующих `N` строк содержит по `M` символов – первоначальный план выделения участков. Символ '#' обозначает участок, выделенный под строительство, а символ '.' – свободный участок.

Первая строка вывода должна содержать два целых числа `R` и `C` (`1\ ≤\ R,\ C\ ≤\ 40`). Далее должно быть `R` строк, содержащих по `C` символов — предлагаемые изменения в плане. Символ '#' означает участок, выделенный под строительство как в оригинальном, так и в исправленном плане. Символ '+' означает участок, который был свободным в оригинальном плане, но выделенный под строительство в новом плане. Символ '-' означает участок, ставший свободным в новом плане, а символ '.' – свободный участок в обоих планах.

2 3
#.#
###

4 3
...
-+#
###
...