Top This
Игра "Top This" проводится с фигурами, состоящими из четырех единичных квадратов, расположенных так, чтобы каждый квадрат делил сторону хотя бы с одним другим квадратом. Это приводит к следующим семи фигурам:
Вам дается три красные фигуры и три синие фигуры. Ваша цель — разместить три красные фигуры на сетке так, чтобы они не перекрывали друг друга (но могут касаться сторонами), а затем расположить три синие фигуры поверх красных так, чтобы они покрывали точно те же квадраты.
Например, предположим, что наши красные фигуры включают форму B и две копии формы C, а наши синие фигуры — форма B, форма D и форма E. Мы могли бы создать идентичные формы, комбинируя их следующим образом:
Обратите внимание, что вы можете поворачивать каждую фигуру независимо в любое выбранное вами положение. Однако переворачивать фигуру нельзя. (Это изменило бы фигуру формы B на фигуру формы D и наоборот; аналогично это поменяло бы E и G.)
Ваша задача — решить головоломку "Top This" и сообщить о форме, которую можно создать из обеих групп фигур, если это возможно. Мы дополнительно ограничиваем задачу, рассматривая только решения, которые можно разместить на сетке шесть на шесть. Возможно, что будет более одного решения головоломки — и даже если есть только одно решение, будет много различных позиций и ориентаций, в которых форма может находиться. Вы должны указать форму, которая идет первой на основе следующего порядка:
Даны два решения, исследуйте квадраты в порядке строк (т.е. слева направо в каждой строке, начиная с верхней строки), пока не найдете первый квадрат, который отличается между двумя. Решение, в котором квадрат заполнен, идет перед решением, в котором квадрат пуст.
Входные данные
Первая строка ввода содержит число T, где 1 ≤ T ≤ 5. Оставшиеся T строк представляют собой T наборов данных, по одному на строку. Каждый набор данных состоит из строки из трех символов, одного пробела и другой строки из трех символов. Каждый символ будет заглавной буквой от A до G, представляющей одну из семи фигур, обозначенных на Рисунке 1 выше. Первые три символа будут красными фигурами; последние три символа будут синими фигурами.
Выходные данные
Для каждого набора данных вы должны сначала вывести порядковый номер набора данных на отдельной строке: 1 для первого набора, 2 для второго и так далее. После порядкового номера должно следовать решение, напечатанное в виде шести строк с шестью символами в каждой строке. Каждый символ представляет собой единичный квадрат — решетка (#) указывает на заполненный квадрат, а точка (.) указывает на пустой квадрат. Заполненные квадраты должны описывать первую форму, которую можно сформировать как из красных, так и из синих фигур, в соответствии с определенным выше порядком. Если решения нет, просто напечатайте "No solution" на одной строке.