Электрификация
Елена - технолог Расширенной Цепи Мастерства, и она в настоящее время занята проектированием электрической схемы для системы управления светом в гостиничном номере класса люкс.
Схема будет встраиваться в потолок комнаты. Она будет иметь вид прямоугольной сетки, каждая ячейка которой может содержать лишь один элемент. Далее мы приведем список всех возможных элементов с описанием их функций и символов, которыми они задаются.
'.' - пустая ячейка; не имеет никаких входных или выходных сигналов;
'/' - провод; принимает сигнал из левого нижнего угла и передает его в правый верхний;
'\' - провод; принимает сигнал из левого верхнего угла и передает его в правый нижний;
'X' - пересечение; принимает сигнал из верхнего левого и нижнего левого углов и передает его в нижний правый и верхний правый углы соответственно;
'L' - расщепление провода; принимает сигнал из левого нижнего угла и передает его одновременно в верхний левый и нижний правый углы;
'7' - исключающее или; принимает сигнал из левого верхнего угла и левого нижнего угла и передает XOR этих сигналов в верхний правый угол.
Комната отеля имеет n переключателей и m ламп. Переключатели соединены с n точками потолка с левой стороны схемы, а лампы - с m точками потолка с правой стороны. Задача Елены состоит в создании схемы, соединяющей переключатели и лампы согласно следующему руководству.
Дизайнеры комнаты присвоили каждой лампе некоторый набор переключателей. Лампа должна изменять свое состояние (включиться, если была выключена, и выключиться если была включена) каждый раз, когда переключатель, который к ней относится, меняет свое состояние. Лампа не должна изменять свое состояние, если изменяет свое состояние переключатель, который не относится к этой лампе.
Должны выполняться следующие правила соединения проводов:
нижняя левая вершина элемента 'L' должна иметь в точности один входной провод. Каждая из остальных двух вершин должна иметь по одному выходному проводу;
к верхней правой вершине элемента '7' должен быть подсоединен в точности один выходной провод. К каждой из остальных входных вершин должен подходить только один провод;
от каждого переключателя должен исходить только один провод;
к каждой лампе должен быть подведен только один провод;
каждая точка с левой стороны, не соединенная с переключателем, а также каждая точка с правой стороны, не соединенная с лампой, не должны иметь ни входных, ни выходных проводов;
каждая из остальных вершин должна либо не иметь входных и выходных проводов, либо иметь в точности один входной и один выходной провод.
Известно, что схема соединений разработана так, что циклические зависимости невозможны.
Елене задается информация о соединении переключателей и ламп. Помогите ей разработать соответствующую схему.
Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 10) - количество переключателей и ламп, расположенных в обустраиваемой комнате.
Каждая из следующих n строк содержит по m символов. j-ый символ i-ой строки показывает, соединен ли i-ый переключатель с j-ой лампой. Цифра 1 означает "соединен", цифра 0 означает "не соединен".
Каждая лампа соединена как минимум с одним переключателем, каждый переключатель соединен как минимум с одной лампой.
Выходные данные
Первая строка содержит два целых числа h и w, размеры схемы (max(m, n) - 1 ≤ h ≤ 1000; 1 ≤ w ≤ 1000).
Каждая из следующих h строк содержит w символов. Допускаются только символы '.', '/', '\', 'X', 'L', и '7'.
Система должна быть работающей (с точки зрения описанных правил), и удовлетворять соединениям, заданным во входном файле.
Если существует несколько вариантов решения, то следует вывести любой.