Задачі
Задача Лойда
Задача Лойда
Сем Лойд --- видатний американський майстер головоломок. Одна з найвідоміших його головоломок --- це "Гра в п'ятнадцять". Також він відомий як автор великої кількості шахових задач та задач на розрізання. Вам пропонується розв'язати задачу Лойда про розрізання шахової дошки.
Задано шахову дошку розміром \textbf{n}×\textbf{n}. Потрібно розпиляти її на найбільшу кількість частин так, щоб довільні дві частини були різними. Кожна частина повинна складатись з однієї чи декількох клітинок і являти собою зв'язну по стороні фігуру. Частини, які відрізняються лише поворотом, вважабться однаковими. Так, існує дві однокліткових частини: чорна клітинка та біла клітинка, і лише одна частина, яка складається з двох клітинок.
Ось один з розв'язків оригінальної задачі Лойда про розрізання звичайної шахової дошки \textbf{8}×\textbf{8} на \textbf{18} різних частин:
\includegraphics{https://static.e-olymp.com/content/0a/0a21009c9d6ec5ca1668182cac31b72afc63b960.jpg}
\InputFile
У єдиному рядку міститься ціле число \textbf{n}, довжина сторони дошки (\textbf{1} ≤ \textbf{n} ≤ \textbf{30}).
\OutputFile
У першому рядку виведіть максимальну кількість частин, на які можна розрізати дошку. Далі виведіть саме розрізання: \textbf{n} рядків по \textbf{n} маленьких латинських букв у кожному. Кожна частина повинна складатись з однакових букв, при цьому одну і ту ж літеру можна використовувати для позначення декількох частин, але довільні дві сусідні частини повинні складатись з різних букв. Якщо існує більше одного оптимального розрізання, то можна вивести довільне.
Вхідні дані #1
8
Вихідні дані #1
18 aabbaaab aacbbdab bcccdddb baaacccb bbczzacd acazzaad acczzbcd aaczzbcc