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 翻译