You are given an infinite complete binary tree whose vertices are labeled with positive integers. The root is vertex , and for every vertex (), its parent is .
You are also given a string of length . Each character of is either 'L' or 'R'.
Consider the following process: you are currently at some vertex , and want to reach vertex by repeatedly moving through the tree.
On the -th move (1-indexed), suppose you are at vertex . You may choose one of the following moves:
Downward move: If is 'L', move to vertex . Otherwise, move to vertex .
Upward move: You can choose only if . Move to vertex .
Note that you cannot stay at the same vertex.
You are given independent queries. In the -th query, you start at vertex and want to reach vertex .
For each query, determine whether it is possible to reach from . If it is possible, find the minimum number of moves required.
输入格式
The input is given in the following format:
()
and are integers.
is a string of length consisting of 'L' and 'R'.
输出格式
Output lines. On the -th line, print the minimum number of moves required to reach from if it is possible; otherwise, print "-1".
