二叉树上的移动

题目描述

有一棵具有 $2^{10^{100}}-1$ 个顶点的满二叉树,顶点编号为 $1, 2, \dots, 2^{10^{100}}-1$。

顶点 $1$ 是根。对于每个满足 $1 \le i \lt 2^{10^{100}-1}$ 的 $i$,顶点 $i$ 有左孩子顶点 $2i$ 和右孩子顶点 $2i+1$。

高桥从顶点 $X$ 出发,进行由字符串 $S$ 表示的 $N$ 次移动。第 $i$ 次移动如下。

• 如果 $S$ 的第 $i$ 个字符是 U,移动到当前所在顶点的父顶点。
• 如果 $S$ 的第 $i$ 个字符是 L,移动到当前所在顶点的左孩子。
• 如果 $S$ 的第 $i$ 个字符是 R,移动到当前所在顶点的右孩子。

求高桥在 $N$ 次移动后所在的顶点编号。在给定的输入中,保证答案不超过 $10^{18}$。

输入格式

输入按以下格式从标准输入给出:

N X
S

输出格式

输出答案。

样例

3 2
URL

6

在三次移动中,高桥按照 $2 \to 1 \to 3 \to 6$ 移动。

4 500000000000000000
RRUU

500000000000000000

在移动过程中,高桥可能位于编号超过 $10^{18}$ 的顶点。

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371

数据范围

• $1 \le N \le 10^6$
• $1 \le X \le 10^{18}$
• $N$ 和 $X$ 均为整数。
• $S$ 是长度为 $N$ 的、由 U、L 和 R 组成的字符串。
• 高桥位于根时,不会尝试移动到父顶点。
• 高桥位于叶顶点时,不会尝试移动到孩子。
• 高桥在 $N$ 次移动后所在的顶点编号不超过 $10^{18}$。