Інтелектуальна власність#6268
Ераст Копі — відомий дизайнер головоломок Судоку. Його збірники головоломок стали настільки популярними, що з'явилося багато наслідувань і плагіату. Перед тим як звернутися до суду, він вирішив зібрати більше доказів. Головоломка Судоку — це таблиця розміром 9 \times 9, розділена на підтаблиці 3 \times 3, кожна з яких містить 3 \times 3 клітинок. У кожній клітинці може бути цифра від до . Завдання полягає в заповненні порожніх клітинок цифрами так, щоб кожен рядок, стовпець і кожна з підтаблиць 3 \times 3 містила кожну цифру від до лише один раз.
У Копі є база даних головоломок Судоку, і він хоче перевірити, чи є в ній подібні головоломки. Головоломка вважається подібною до головоломки , якщо її можна перетворити на головоломку за допомогою наступних операцій:
вибрати дві цифри і та замінити всі цифри на і навпаки;
переставити дві трійки рядків: (1, 2, 3), (4, 5, 6), (7, 8, 9);
переставити два рядки в одній трійці рядків;
переставити дві трійки стовпців: (1, 2, 3), (4, 5, 6), (7, 8, 9);
переставити два стовпці в одній трійці стовпців;
відобразити по діагоналі з верхнього лівого в нижній правий кут. Після цієї операції стовпці стають рядками і навпаки.
Допоможіть Копі знайти подібні задачі в його базі даних.
Перший рядок містить одне ціле число (1 \le n \le 20) — кількість головоломок у базі даних.
Далі йде опис головоломок: P_1, P_2, \ldots, P_n. Кожна головоломка описується дев'ятьма рядками, що містять дев'ять символів кожен. Кожен символ — це або цифра від до , або крапка (.), що позначає порожню клітинку. Порожній рядок відокремлює послідовні головоломки в базі даних.
Пробілів у вхідних даних немає.
Головоломки не обов'язково розв'язувані.
Перевірте, чи є головоломка P_i подібною до головоломок P_j (у цьому порядку), де 1 \le i < j \le n.
Якщо головоломка P_i подібна до головоломки P_j, виведіть Yes, інакше виведіть No. Якщо відповідь позитивна, наступний рядок повинен містити ціле число q_{ij} — кількість операцій, необхідних для перетворення головоломки P_i у головоломку P_j. Кількість операцій не обов'язково має бути мінімальною, але не повинна перевищувати . У наступних q_{ij} рядках запишіть операції, що перетворюють головоломку P_i у головоломку P_j, по одній на рядок.
Операції кодуються наступним чином:
D x y для обміну цифрами і ;
R a b для обміну трійок рядків (3a-2, 3a-1, 3a) і (3b-2, 3b-1, 3b);
r a b для обміну рядків і , рядки повинні належати одній трійці рядків;
C a b для обміну трійок стовпців (3a-2, 3a-1, 3a) і (3b-2, 3b-1, 3b);
c a b для обміну стовпців і , стовпці повинні належати одній трійці стовпців;
F для відображення по діагоналі з верхнього лівого в нижній правий кут.
Стовпці нумеруються зліва направо, а рядки нумеруються зверху вниз, як вони дані у вхідних даних, починаючи з першого.
Приклад 1