魔法金字塔

题目背景

著名的魔方有许多变体，其中一种叫作魔法金字塔。它不是立方体，而是一个正四面体。

正四面体的四个面分别用大写字母 X、U、V、W 标记。每个面被划分成 $9$ 个小等边三角形，全部 $36$ 个小三角形按照图 1 编号。

将图中的大三角形沿内部粗线向下折叠，再把外部粗线的对应半边粘合，就能组成这个正四面体。

图 1：小三角形的编号以及四个面的标记

图 1：小三角形的编号以及四个面的标记

每个小三角形都被染成 a、b、c、d 四种颜色之一，并且每种颜色恰好出现 $9$ 次。

题目描述

你可以使用以下两类操作改变魔法金字塔的状态。

1. 旋转一个面

选择四个面中的一个，并将金字塔摆放成所选面正对着你。然后选择顺时针或逆时针方向，将靠近该面的、厚度为整个四面体高度 $\frac13$ 的部分沿所选方向旋转 $120^\circ$，其余部分保持不动。

图 2 展示了将 U 面顺时针旋转后的效果。图中的数字表示旋转前位于对应编号位置的小三角形。

图 2：U 面顺时针旋转后的效果

图 2：`U` 面顺时针旋转后的效果

在输出中：

• 小写字母 x、u、v、w 分别表示对应面的顺时针旋转；
• 大写字母 X、U、V、W 分别表示对应面的逆时针旋转。

2. 魔法重染色

魔法重染色操作由整数 $1$ 到 $36$ 的一个排列

$$(p_1,p_2,\ldots,p_{36})$$

定义。

执行该操作时，编号为 $i$ 的位置会被重新染成操作前编号为 $p_i$ 的位置的颜色。全部 $36$ 个位置同时完成重染色。

在输出中，魔法重染色操作用字符 * 表示。

完成条件

当正四面体的每一个面上，全部 $9$ 个小三角形都具有相同颜色时，称魔法金字塔已经完成。

请使用尽可能少的操作完成魔法金字塔，并输出一组最短操作序列。

保证所有测试数据都能在不超过 $9$ 次操作内完成。

输入格式

输入共两行。

第一行包含一个长度为 $36$ 的字符串，只由字符 a、b、c、d 组成。第 $i$ 个字符表示编号为 $i$ 的小三角形的初始颜色。

保证四种字符在第一行中均恰好出现 $9$ 次。

第二行包含 $36$ 个两两不同的整数 $p_1,p_2,\ldots,p_{36}$，它们构成 $1$ 到 $36$ 的一个排列，用于定义魔法重染色操作。

输出格式

输出一行字符串，只能包含以下字符：

X U V W x u v w *

字符串的第 $i$ 个字符表示第 $i$ 次操作：

• 小写字母表示将对应面顺时针旋转；
• 大写字母表示将对应面逆时针旋转；
• * 表示执行一次魔法重染色。

输出的操作次数必须最少。如果存在多组最短方案，输出任意一组即可。

如果初始状态已经完成，请输出一个空行。

样例

输入

ddddcccccabbbbbdcaabbbddacccaabddaaa
36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

输出

*U

样例解释

图 3 表示初始状态，图 4 表示执行魔法重染色 * 后的状态，图 5 表示随后将 U 面逆时针旋转后的状态。

图中的纹理分别表示颜色：a 为横线、b 为竖线、c 为斜线、d 为点纹。

图 3：初始状态

图 4：执行 `*` 后的状态

图 5：随后执行 `U` 后的完成状态

数据范围

• 初始颜色串长度为 $36$；
• a、b、c、d 均恰好出现 $9$ 次；
• $(p_1,p_2,\ldots,p_{36})$ 是 $1$ 到 $36$ 的排列；
• 最短答案长度不超过 $9$。

时间与空间限制

• 时间限制：$2\text{ s}$
• 空间限制：$64\text{ MB}$