题目描述

頂点数 $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}$ 以下になるような入力のみが与えられます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $S$

输出格式

答えを出力せよ。

题目大意

有一棵 $(2^{10^{100}}-1)$ 个结点的完全二叉树，根结点为 $1$，结点 $i(1\le i < 2^{10^{100}}-1)$ 的左子结点为 $2i$，右子结点为 $2i+1$。
高桥君从结点 $X$ 开始进行 $N$ 次移动，每次移动用一个字符表示：

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

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

3 2
URL

6

4 500000000000000000
RRUU

500000000000000000

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

126419752371

提示

制約

• $1\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ X\ \leq\ 10^{18}$
• $N,X$ は整数
• $S$ は長さ $N$ であり、U,L,R のみからなる
• 高橋君が根にいるとき、親に移動しようとすることはない
• 高橋君が葉にいるとき、子に移動しようとすることはない
• 高橋君が $N$ 回の移動後にいる頂点の番号は $10^{18}$ 以下である

Sample Explanation 1

完全二分木は次のような構造をしています。  各移動により、高橋君がいる頂点の番号は $2\ \to\ 1\ \to\ 3\ \to\ 6$ と変化します。

Sample Explanation 2

移動の途中過程において、高橋君がいる頂点の番号が $10^{18}$ を超えることもあります。