[CEOI2013]Board

题目描述

给出这样一棵“二叉树”: - 每个节点有左右两个儿子,并如下定义每个节点的高度:假设父亲节点的高度为 $h$,那么他的两个儿子的节点的高度都是 $h+1$,相同高度的所有节点称作一层。 - 每个节点的左儿子的子树都在右儿子的子树的左边,每一层相邻的两个节点之间有一条边。 下面是一个例子: ![](https://cdn.luogu.com.cn/upload/pic/74384.png) 每一条图上的路径用一个字符串表示,字符串中的每一个字符表示一 个移动。字符仅包含如下五种: - $1$:表示移动到当前节点的左儿子 - $2$:表示移动到当前节点的右儿子 - $U$:表示移动到当前节点的父亲节点 - $L$:表示移动到当前节点同层的左边的节点(保证当前节点在这一层中不是最左边的节点) - $R$:表示移动到当前节点同层的右边的节点(保证当前节点在这一层中不是最右边的节点) 用一条路径来表示这条路径的终点,例如路径:$221LU$ 就表示上图中的节点A。 给出两条路径,你的任务是求出着两条路径的终点之间的最短路。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

221LU
12L2

输出样例 #1

3

输入样例 #2

111RRRRRRR
222

输出样例 #2

0

输入样例 #3

11111
222222

输出样例 #3

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$。