该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件读写

本题使用文件输入输出，请在程序开头加入：

freopen("treedis.in", "r", stdin);
freopen("treedis.out", "w", stdout);

题目描述

徐老师和石老师为了反抗老板的压榨，决定在公司内部的每个部门进行游行！

公司内部的的部门布局类似于一棵倒着的满二叉树

1. 我们把大门也当成一个部门，编号为 $1$，处于第 $1$ 层
2. 每个编号为 $i$ 的部门有两个子部门，左侧部门编号为 $i * 2$，右侧部门编号为 $i * 2 + 1$，且 $i$ 号部门分别有一条通道连接到这两个子部门，可以通过通道往返于 i 号部门和子部门之间
3. 如果 $i$ 号部门处在第 $x$ 层，那么它的两个子部门就处在 $x + 1$ 层
4. 如果两个部门的编号相差 $1$，且它们处于同一层，那么它们之间存在一条通道，可以通过这条通道往返这两个部门
5. 你可以认为这家公司的部门有无限多个

现在为了不被别人发现，徐老师决定使用暗语和石老师沟通游行路线

这个暗语会是一个字符串，从左往右依次表示每一次行动的方向

其中：

• $1$： 表示移动到当前部门的左侧子部门
• $2$： 表示移动到当前部门的右侧子部门
• $U$： 表示移动到当前部门的上层部门，例如 $5$ 号部门的上层部门是 $2$
• $L$： 表示移动到当前部门同层的左边那个部门（保证当前部门不会是这层最左侧的部门）
• $R$： 表示移动到当前部门同层的右边那个部门（保证当前部门不会是这层最右侧的部门）

现在徐老师和石老师已经分别告知了对方自己的游行路线

现在徐老师想知道，他们两个在游行结束后，最少需要移动几个部门才能找到对方？（以便于快速跑路）

输入格式

输入第一行包含一个字符串，表示徐老师的游行路线

输入第二行包含一个字符串，表示石老师的游行路线

输出格式

输出一个整数，表示最终答案

数据范围

设 $H$ 表示两人游行路线中会到达的最高层部门的层数，$len$ 表示游行路线字符串的长度

对于 $30\%$ 的数据保证：$1 \leq H \leq 10,1 \leq len \leq 100$；

对于 $60\%$ 的数据保证：$1 \leq H \leq 30,1 \leq len \leq 100$；

对于 $100\%$ 的数据保证：$1 \leq H \leq 50,1 \leq len \leq 100000$；

特别的，保证对于每段测试数据中的第一组数据，徐老师和石老师的终点是同一个部门

221LU
12L2

3

样例解释1

他们的行进路线如下

前 $4$ 层的部门编号排布为：

同一层中编号相邻的两个部门之间存在通道。样例 1 中两人路线为：

• 徐老师 221LU：$1 \to 3 \to 7 \to 14 \to 13 \to 6$
• 石老师 12L2：$1 \to 2 \to 5 \to 4 \to 9$

终点 $6$ 与 $9$ 之间最少移动 $3$ 次：$6 \to 3 \to 4 \to 9$（依次为 U、L、2 操作）

可以发现最终两人之间相距 $3$ 次移动的距离

111RRRRRRR
222

0

11111
222222

10