C. 树上行走

题目描述

有一棵 $(2^{10^{19}} - 1)$ 个结点的完全二叉树，根结点为 $1$，结点 $i(1 \le i < 2^{10^{19}} - 1)$ 的左子结点为 $2i$，右子结点为 $2i + 1$。

高桥君从结点 $X$ 开始进行 $N$ 次移动，每次移动用一个字符表示：

• U：移动到当前结点的父结点。
• L：移动到当前结点的左子结点。
• R：移动到当前结点的右子结点。

移动序列为一个长度为 $N$ 的字符串 $S$。给定 $N, X, S$，求按照 $S$ 依次进行 $N$ 次移动后高桥所处的结点编号。

输入格式

N X
S

输出格式

输出最终所在节点的编号。

样例

输入样例 #1

3 2
URL

输出样例 #1

6

输入样例 #2

4 500000000000000000
RRUU

输出样例 #2

500000000000000000

输入样例 #3

30 123456789
LRULURLURLULULRURRLRULRRRUU RRU

（注：原序列无空格，此处为排版展示）

输出样例 #3

126419752371

数据范围与提示

• $1 \le N \le 10^6$
• $1 \le X \le 10^{18}$
• $N, X$ 是整数
• $S$ 只包括 U, L, R
• 保证在根节点时不会走 U
• 保证最终答案不超过 $10^{18}$（中间过程可能超过）