Problem Description

Consider a "binary tree" where:
- Each node has two children, a left and a right child. The height of each node is defined as follows: if the height of the parent node is \( h \), then the heights of the two children are both \( h+1 \). All nodes with the same height are considered to be on the same level.
- The subtree of the left child of a node is to the left of the subtree of the right child. Adjacent nodes on the same level are connected by an edge. Below is an example:

Each path in the tree is represented by a string, where each character in the string denotes a move. The characters can be one of the following five types:
- \(\tt 1\): Move to the left child of the current node.
- \(\tt 2\): Move to the right child of the current node.
- \(\tt U\): Move to the parent of the current node.
- \(\tt L\): Move to the left node on the same level (guaranteed that the current node is not the leftmost on this level).
- \(\tt R\): Move to the right node on the same level (guaranteed that the current node is not the rightmost on this level).

A path represents the destination node of that path. For example, the path \(\tt 221LU\) represents node \(A\) in the diagram. Given two paths, your task is to find the shortest path between the destination nodes of these two paths.

Input Format

The input consists of two lines, each containing a string representing a path.

Output Format

Output a single line representing the shortest path between the two nodes.

Sample Input and Output

Sample Input #1

221LU
12L2

Sample Output #1

3

Sample Input #2

111RRRRRRR
222

Sample Output #2

0

Sample Input #3

11111
222222

Sample Output #3

10

Notes

Let \( D \) denote the maximum depth of any node traversed, and \( S \) denote the maximum length of the input strings.

• For 10% of the test cases, \( D \leq 10 \).
• For 30% of the test cases, \( D \leq 50 \).
• For 50% of the test cases, \( D \leq 10^3 \).
• For 70% of the test cases, \( D \leq 2 \times 10^4 \).
• For 100% of the test cases, \( D \leq 10^5, S \leq 10^5 \).

见题面 Input 部分

见题面 Output 部分