Магічна піраміда
Існує багато варіацій відомої головоломки Кубик Рубіка. Одна з них, під назвою Магічна Піраміда, базується на тетраедрі замість куба. Грані тетраедра позначені латинськими літерами X, U, V та W. Кожна грань розділена на 9 рівносторонніх трикутників, пронумерованих від 1 до 36, як показано на Рисунку 1. Щоб зібрати тетраедр, великий трикутник потрібно скласти вниз уздовж внутрішніх товстих ліній, а відповідні половинки зовнішніх товстих ліній склеїти разом.
Кожен з малих трикутників пофарбований в один з чотирьох різних кольорів, які ми
Рис. 1
позначаємо латинськими літерами a, b, c та d. Є рівно 9 трикутників кожного з чотирьох кольорів.
Ми можемо трансформувати тетраедр, використовуючи операцію «обертання грані». Щоб виконати цю операцію, виберіть грань піраміди і орієнтуйте піраміду так, щоб вибрана грань була спрямована до вас. Потім визначте напрямок обертання (за годинниковою стрілкою або проти годинникової стрілки). Нарешті, поверніть частину тетраедра, найближчу до вибраної грані, товщиною 1/3 висоти тетраедра на 120 градусів у вибраному напрямку, залишаючи решту частини тетраедра нерухомою. Рисунок 2 ілюструє ефект обертання грані U за годинниковою стрілкою.
Окрім обертання граней, ми також можемо застосувати операцію «магічне перефарбування». Ця операція визначається перестановкою (p_1, …, p_36) цілих чисел від 1 до 36. Ефект операції полягає в тому, що трикутник, який зараз знаходиться на позиції i (згідно з нумерацією, наведеною на Рисунку 1), перефарбовується в колір трикутника, який зараз знаходиться на позиції p_{i} (згідно з тією ж нумерацією). Усі 36 трикутників перефарбовуються одночасно.
Головоломка вважається розв'язаною, якщо після застосування певної кількості операцій «обертання грані» та/або «магічне перефарбування» всі трикутники на кожній грані тетраедра мають один і той самий колір.
Напишіть програму для розв'язання головоломки Магічна Піраміда, використовуючи мінімально можливу кількість ходів. Ви можете припустити, що всі тестові випадки можна розв'язати за 9 або менше ходів.
Вхідні дані
Перша строка файлу містить 36 літер 'a'…'d'. Літера на позиції i позначає початковий колір трикутника номер i. Відомо, що кожна з чотирьох літер зустрічається рівно 9 разів у першій строкі файлу.
Друга строка файлу містить 36 різних цілих чисел 1…36, які описують операцію "магічного перефарбування". i-те число в цій строкі є членом p_i перестановки, яка визначає операцію.
Вихідні дані
Перша і єдина строка файлу повинна містити рядок символів 'X', 'U', 'V', 'W', 'x', 'u', 'v', 'w', і '*'. i-й символ повинен описувати i-й хід у розв'язанні головоломки. Кожна операція "обертання грані" позначається як літера відповідної грані, причому маленька літера позначає поворот за годинниковою стрілкою, а велика літера — проти годинникової стрілки. Операція "магічне перефарбування" позначається символом '*'.
Якщо існує кілька розв'язків з мінімальною кількістю ходів, виведіть будь-який з них. Якщо головоломку можна розв'язати без жодного ходу, виведіть порожній рядок у файл.
Пояснення прикладу: Рисунок 3 показує початкове забарвлення тетраедра, а Рисунки 4 та 5 показують результати кожної операції. Кольори трикутників задані наступними шаблонами:
