UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3342. [Ceoi2013]board

Statistics 下载数据

Description

Mirko and Slavko have a new board game. The game board resembles a complete infinite binary tree. More precisely, the board consists of nodes and two-way roads connecting them. The root node is located at the
top of the board and we say it is at    level zero. Each node has exactly two children, the     left child and the
right child , located in the lower-left and the lower-right directions of the parent node. The level of a
child node is one greater than the level of the parent node. In addition to roads connecting a parent node with its children, there are roads connecting all of the nodes at a particular level – for each level, starting from the leftmost node, there is a road connecting each node to the next node to the right on the same level.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Figure 1: The second test example below
 
Each path through the game board is a sequence of steps, each moving from a node to a different node via
a single road. Each step can be described by a single character as follows:
·  character „1 describes moving from a node to its left child,
·  character „2 describes moving from a node to its right child,
·  character „U describes moving from a node to its parent,
·  character „L describes moving from a node to the next node to the left on the same level,
·  character „R describes moving from a node to the next node to the right on the same level.
For example, if we were to start at the root node and take the sequence of steps „221LU we would end up in the node denoted with the letter „A in the figure above.
 
 
TASK
Write a program that will, given two nodes on the board, find the smallest number of steps needed to go from one node to the other. The two nodes are given by specifying paths from the root node to them. If the two paths lead to the same node, the answer is zero.

Input

The first line of input contains a sequence of at most 100 000 characters – the path from the root to the first node.

The second line of input contains a sequence of at most 100 000 characters – the path from the root to the second node.

The two paths will be valid (it will be possible to make every move in both sequences).

Output

The first and only line of output should contain a single integer - the smallest number of steps needed to go from one node to the other.

Sample Input

221LU
12L2

Sample Output

3

Hint

Source