题目描述

给你一棵巨大（实际上是无限大）的特殊二叉树：

• 每个节点都有两个儿子：左儿子与右儿子
• 关于节点的高度与层：假设当前节点为 $h$，那么当前节点的儿子节点的高度都是 $h+1$，相同高度的所有节点为同一层。
• 每个节点的左儿子的子树都在右儿子的子树的左边，每一层相邻的两个节点之间有一条边。 下面是一个例子：

对于树上的点，可以采用从根节点走到它的路径的形式描述。路径用下面的五种字符组成的字符串描述，字符串中的每一个字符表示一次移动：

• $1$：表示移动到当前点的左儿子
• $2$：表示移动到当前点的右儿子
• $U$：表示移动到当前点的父节点（保证当前点一定不是根节点）
• $L$：表示移动到当前点同层的左边的节点（保证当前点在这一层中不是最左边的）
• $R$：表示移动到当前点同层的右边的节点（保证当前点在这一层中不是最右边的）

图上的 $A$ 点可以用 $221LU$ 表示。

给你两条路径，请求出着两条路径的终点之间的最短路。

输入格式

输入两行，每行一个字符串，表示两条路径。

输出格式

输出一行，两个节点之间的最短路。

221LU
12L2

3

111RRRRRRR
222

0

11111
222222

10

提示

用 $D$ 表示所有经过的节点中，深度最大的节点的深度；$S$ 表示输入字符串的最大长度。

对于 $100\%$ 的数据，$D \leq 10^5, S \leq 10^5$。

• 子任务 1（20 分）：$D \leq 10$;
• 子任务 2（20 分）：$D \leq 50$;
• 子任务 3（30 分）：$D \leq 10^3$;
• 子任务 4（30 分）：无特殊限制