当前没有测试数据。

D - 二叉树移动

得分：$400$ 分

问题描述

有一棵完美二叉树，具有 $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$

输出

输出答案。

3 2
URL

6

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

在这三次移动中，高桥经过顶点 $2 \to 1 \to 3 \to 6$。

4 500000000000000000
RRUU

500000000000000000

在过程中，高桥可能到达的顶点索引超过了 $10^{18}$。

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371