Широко известна задача о количестве замощений доминошками размера 1 × 2 поля размера 2 × n. Возможно, вы помните, что она сводится к числам Фибоначчи. Ниже речь пойдет о другой задаче, в которой вам тоже предстоит иметь дело с замощениями доминошками прямоугольного поля.
Задано прямоугольное поле размера 4 × n, то есть такое, которое содержит четыре строки и n столбцов. Требуется найти любое такое его замощение доминошками 1 × 2, что каждый из n - 1 возможных вертикальных разрезов по линиям сетки пересекает хотя бы одну доминошку, разделяя ее пополам. Никакие две доминошки в искомом замощении не должны накладываться, каждая клетка поля должна быть покрыта ровно одной доминошкой. Доминошки разрешается поворачивать, то есть можно использовать как доминошки 2 × 1, так и 1 × 2.
Напишите программу, которая находит произвольное искомое замощение.
Выходные данные
Если решения не существует, выведите «-1» (без кавычек). Иначе выведите четыре строки по n символов в каждой — описание замощения, в котором каждый вертикальный разрез пересекает хотя бы одну доминошку. Замощение следует выводить, раскрасив поле в не более чем 26 цветов. Каждую доминошку нужно покрасить в один цвет. Разные доминошки могут быть покрашены в один и тот же цвет, но доминошки одного цвета не должны касаться по стороне. Для обозначения цветов нужно использовать строчные буквы латинского алфавита. Выведите любой из допустимых способов замощения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
yyzz
bccd
bxxd
yyaa
|