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

Озимандия нажал кнопку самоуничтожения базы в Антарктиде, перепутал элементы схемы пульта управления и сбежал. Роршах должен восстановить схему, поворачивая элементы таким образом, чтобы все элементы были соединены снова, и отключить систему самоуничтожения базы.

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

Первая строка ввода содержит два целых числа `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 8`) – размеры схемы пульта управления. Далее следует `N` строк, в каждой строке `M` символов. Символ 'i' означает элемент, у которого один выход, символ 'r' означает элемент, у которого два выхода под углом 90 градусов, символ '-' означает элемент, у которого два выхода под углом 180 градусов, символ 'T' означает элемент, у которого три выхода, а символ '+' означает элемент, у которого четыре выхода.

Суммарное количество выходов у всех элементов равно `2*(N*M-1)`. Гарантируется, что, поворачивая элементы, их можно соединить между собой таким образом, что каждый выход у всех элементов будет соединен с каким-то выходом другого элемента и все элементы будут прямо или через другие соединены между собой. Между двумя элементами схемы будет ровно один путь по соединениям.

Вывести `2*N-1` строк по `2*M-1` символов. Соединяемые элементы обозначить символом '*', соединения между ними – символами '-' и '|', пустое место – символом '.'. Если существует несколько вариантов соединения, то можно вывести любой из них.

3 4
riii
T-+r
riri

*-*.*.*
|...|.|
*-*-*-*
|...|..
*-*.*-*