Магічна піраміда

Існує багато варіацій відомої головоломки Кубик Рубіка. Одна з них, під назвою Магічна Піраміда, базується на тетраедрі замість куба. Грані тетраедра позначені латинськими літерами X, U, V та W. Кожна грань розділена на $9$ рівносторонніх трикутників, пронумерованих від $1$ до $36$, як показано на Рисунку 1. Щоб зібрати тетраедр, великий трикутник потрібно скласти вниз уздовж внутрішніх товстих ліній, а відповідні половинки зовнішніх товстих ліній склеїти разом.

Кожен з малих трикутників пофарбований в один з чотирьох різних кольорів, які ми

Рис. 1

позначаємо латинськими літерами a, b, c та d. Є рівно $9$ трикутників кожного з чотирьох кольорів.

Ми можемо трансформувати тетраедр, використовуючи операцію «обертання грані». Щоб виконати цю операцію, виберіть грань піраміди і орієнтуйте піраміду так, щоб вибрана грань була спрямована до вас. Потім визначте напрямок обертання (за годинниковою стрілкою або проти годинникової стрілки). Нарешті, поверніть частину тетраедра, найближчу до вибраної грані, товщиною $1/3$ висоти тетраедра на $120$ градусів у вибраному напрямку, залишаючи решту частини тетраедра нерухомою. Рисунок 2 ілюструє ефект обертання грані U за годинниковою стрілкою.

Окрім обертання граней, ми також можемо застосувати операцію «магічне перефарбування». Ця операція визначається перестановкою (p_1, \ldots, p_{36}) цілих чисел від $1$ до $36$. Ефект операції полягає в тому, що трикутник, який зараз знаходиться на позиції $i$ (згідно з нумерацією, наведеною на Рисунку 1), перефарбовується в колір трикутника, який зараз знаходиться на позиції p_i (згідно з тією ж нумерацією). Усі $36$ трикутників перефарбовуються одночасно.

Головоломка вважається розв'язаною, якщо після застосування певної кількості операцій «обертання грані» та/або «магічне перефарбування» всі трикутники на кожній грані тетраедра мають один і той самий колір.

Напишіть програму для розв'язання головоломки Магічна Піраміда, використовуючи мінімально можливу кількість ходів. Ви можете припустити, що всі тестові випадки можна розв'язати за $9$ або менше ходів.

Вихідні дані

Перший і єдиний рядок файлу повинен містити рядок символів 'X', 'U', 'V', 'W', 'x', 'u', 'v', 'w', і '*'. $i$-й символ повинен описувати $i$-й хід у розв'язанні головоломки. Кожна операція "обертання грані" позначається як літера відповідної грані, причому маленька літера позначає поворот за годинниковою стрілкою, а велика літера — проти годинникової стрілки. Операція "магічне перефарбування" позначається символом '*'.

Якщо існує кілька розв'язків з мінімальною кількістю ходів, виведіть будь-який з них. Якщо головоломку можна розв'язати без жодного ходу, виведіть порожній рядок у файл.

Пояснення прикладу: Рисунок 3 показує початкове забарвлення тетраедра, а Рисунки 4 та 5 показують результати кожної операції. Кольори трикутників задані наступними шаблонами: