AT_abc243_d [ABC243D] Moves on Binary Tree

[problemUrl]: https://atcoder.jp/contests/abc243/tasks/abc243_d 頂点数 $ 2^{10^{100}}-1 $ の完全二分木があり、頂点には $ 1,2,...,2^{10^{100}}-1 $ の番号がついています。 頂点 $ 1 $ が根であり、各 $ 1\leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ 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} $ 以下である ### Sample Explanation 1 完全二分木は次のような構造をしています。 !\[図\](https://img.atcoder.jp/ghi/9e199e154f481af436c8eaec9c487e2c.png) 各移動により、高橋君がいる頂点の番号は $ 2\ \to\ 1\ \to\ 3\ \to\ 6 $ と変化します。 ### Sample Explanation 2 移動の途中過程において、高橋君がいる頂点の番号が $ 10^{18} $ を超えることもあります。