AT_abc243_d.[ABC243D] Moves on Binary Tree

有一棵顶点数为 $2^{10^{100}}-1$ 的完全二叉树，每个顶点编号为 $1,2,\ldots,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}$。

输入从标准输入读入，格式如下：

$N$ $X$ $S$

输出答案。

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 10^{18}$
• $N, X$ 均为整数
• $S$ 的长度为 $N$，且仅包含 U、L、R
• 当高桥君在根节点时，不会尝试向父节点移动
• 当高桥君在叶节点时，不会尝试向子节点移动
• 高桥君经过 $N$ 次移动后所在的顶点编号不会超过 $10^{18}$

样例解释 1

完全二叉树的结构如下所示。

每次移动后，高桥君所在的顶点编号依次为 $2 \to 1 \to 3 \to 6$。

样例解释 2

在移动过程中，高桥君所在的顶点编号可能会超过 $10^{18}$。

由 ChatGPT 4.1 翻译