题目描述

给出这样一棵“二叉树”:

• 每个节点有左右两个儿子，并如下定义每个节点的高度：假设父亲节点的高度为 $h$，那么他的两个儿子的节点的高度都是 $h+1$，相同高度的所有节点称作一层。

• 每个节点的左儿子的子树都在右儿子的子树的左边，每一层相邻的两个节点之间有一条边。 下面是一个例子：

每一条图上的路径用一个字符串表示，字符串中的每一个字符表示一 个移动。字符仅包含如下五种：

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

用一条路径来表示这条路径的终点，例如路径：$\tt 221LU$ 就表示上图中的节点 $A$。 给出两条路径，你的任务是求出着两条路径的终点之间的最短路。

输入格式

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

输出格式

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

221LU
12L2

3

111RRRRRRR
222

0

11111
222222

10

提示

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

• 对于 $10\%$ 的数据，$D \leq 10$;
• 对于 $30\%$ 的数据，$D \leq 50$;
• 对于 $50\%$ 的数据，$D \leq 10^3$;
• 对于 $70\%$ 的数据，$D\leq 2 \times 10^4$;
• 对于 $100\%$ 的数据，$D \leq 10^5, S \leq 10^5$。