102433: [AtCoder]ABC243 D - Moves on Binary Tree

Problem Statement

There is a perfect binary tree with $2^{10^{100}}-1$ vertices, numbered $1,2,...,2^{10^{100}}-1$.
Vertex $1$ is the root. For each $1\leq i < 2^{10^{100}-1}$, Vertex $i$ has two children: Vertex $2i$ to the left and Vertex $2i+1$ to the right.

Takahashi starts at Vertex $X$ and performs $N$ moves, represented by a string $S$. The $i$-th move is as follows.

• If the $i$-th character of $S$ is U, go to the parent of the vertex he is on now.
• If the $i$-th character of $S$ is L, go to the left child of the vertex he is on now.
• If the $i$-th character of $S$ is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after $N$ moves. In the given cases, it is guaranteed that the answer is at most $10^{18}$.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N$ and $X$ are integers.
• $S$ has a length of $N$ and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after $N$ moves is at most $10^{18}$.

Input

Input is given from Standard Input in the following format:

$N$ $X$
$S$

Output

Print the answer.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes $2 \to 1 \to 3 \to 6$.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds $10^{18}$.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

问题描述

有一个完美的二叉树，有$2^{10^{100}}-1$个顶点，编号为$1,2,...,2^{10^{100}}-1$。
顶点$1$是根。对于每个$1\leq i < 2^{10^{100}-1}$，顶点$i$有两个子顶点：左侧的顶点$2i$和右侧的顶点$2i+1$。

高桥同学从顶点$X$开始进行$N$次移动，由字符串$S$表示。第$i$次移动如下。

• 如果字符串$S$的第$i$个字符为U，则移动到他现在所在顶点的父顶点。
• 如果字符串$S$的第$i$个字符为L，则移动到他现在所在顶点的左子顶点。
• 如果字符串$S$的第$i$个字符为R，则移动到他现在所在顶点的右子顶点。

在$N$次移动后，找出高桥同学所在的顶点的索引。在给定的案例中，答案保证不超过$10^{18}$。

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N$和$X$为整数。
• $S$的长度为$N$，由U、L和R组成。
• 当高桥同学在根顶点时，他不会尝试移动到父顶点。
• 当高桥同学在叶子顶点时，他不会尝试移动到子顶点。
• 在$N$次移动后，高桥同学所在的顶点的索引不超过$10^{18}$。

输入

输入以标准输入的以下格式给出：

$N$ $X$
$S$

输出

打印答案。

样例输入 1

3 2
URL

样例输出 1

6

完美的二叉树具有以下结构。

在三次移动中，高桥同学依次经过$2 \to 1 \to 3 \to 6$。

样例输入 2

4 500000000000000000
RRUU

样例输出 2

500000000000000000

在过程中，高桥同学可能在索引超过$10^{18}$的顶点上。

样例输入 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

样例输出 3

126419752371