Інтелектуальна власність
Ераст Копі — відомий дизайнер головоломок Судоку. Його збірники головоломок стали настільки популярними, що з'явилося багато наслідувань і плагіату. Перед тим як звернутися до суду, він вирішив зібрати більше доказів. Головоломка Судоку — це таблиця розміром 9 × 9, розділена на підтаблиці 3 × 3, кожна з яких містить 3 × 3 клітинок. У кожній клітинці може бути цифра від 1 до 9. Завдання полягає в заповненні порожніх клітинок цифрами так, щоб кожен рядок, стовпець і кожна з 9 підтаблиць 3 × 3 містила кожну цифру від 1 до 9 лише один раз.
У Копі є база даних головоломок Судоку, і він хоче перевірити, чи є в ній подібні головоломки. Головоломка P вважається подібною до головоломки Q, якщо її можна перетворити на головоломку Q за допомогою наступних операцій:
вибрати дві цифри x і y та замінити всі цифри x на y і навпаки;
переставити дві трійки рядків: (1, 2, 3), (4, 5, 6), (7, 8, 9);
переставити два рядки в одній трійці рядків;
переставити дві трійки стовпців: (1, 2, 3), (4, 5, 6), (7, 8, 9);
переставити два стовпці в одній трійці стовпців;
відобразити по діагоналі з верхнього лівого в нижній правий кут. Після цієї операції стовпці стають рядками і навпаки.
Допоможіть Копі знайти подібні задачі в його базі даних.
Вхідні дані
Перша лінія містить одне ціле число n (1 ≤ n ≤ 20) — кількість головоломок у базі даних.
Далі йде опис n головоломок: P[1], P[2], ..., P[n]. Кожна головоломка описується дев'ятьма рядками, що містять дев'ять символів кожен. Кожен символ — це або цифра від 1 до 9, або крапка ('.'), що позначає порожню клітинку. Порожній рядок відокремлює послідовні головоломки в базі даних.
Головоломки не обов'язково розв'язувані.
Вихідні дані
Перевірте, чи є головоломка P[1] подібною до головоломок P[2], P[3], ..., P[n] (у цьому порядку), потім перевірте, чи є головоломка P[2] подібною до головоломок P[3], P[4], ..., P[n] (у цьому порядку) і так далі.
Якщо головоломка P[i] подібна до головоломки P[j] (1 ≤ i < j ≤ n), виведіть "Yes", інакше виведіть "No". Якщо відповідь позитивна, наступний рядок повинен містити ціле число q[ij] — кількість операцій, необхідних для перетворення головоломки P[i] у головоломку P[j]. Кількість операцій не обов'язково має бути мінімальною, але не повинна перевищувати 1000. У наступних q[ij] рядках запишіть операції, що перетворюють головоломку P[i] у головоломку P[j], по одній на рядок.
Операції кодуються наступним чином:
"D x y" для обміну цифрами x і y;
"R a b" для обміну трійок рядків (3a-2, 3a-1, 3a) і (3b-2, 3b-1, 3b);
"r a b" для обміну рядків
aіb, рядки повинні належати одній трійці рядків;"C a b" для обміну трійок стовпців (3a-2, 3a-1, 3a) і (3b-2, 3b-1, 3b);
"c a b" для обміну стовпців a і b, стовпці повинні належати одній трійці стовпців;
"F" для відображення по діагоналі з верхнього лівого в нижній правий кут.
Стовпці нумеруються зліва направо, а рядки нумеруються зверху вниз, як вони дані у вхідних даних, починаючи з першої.