← 返回题目列表

AtCoder · abc243_d

G. 在二叉树上移动

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个完美二叉树 2^{10^{100}}-1 顶点,编号 1,2,...,2^{10^{100}}-1.
顶点 1 是根。对于每个 1\leq i < 2^{10^{100}-1},顶点 i 有两个孩子:Vertex 2i 到左侧和顶点 2i+1 在右边。

Takahashi 从 Vertex 开始 X 并执行 N 移动,用字符串表示 S。的 i第一步移动如下。

  • 如果 i- 第一个字符 S is U,转到他现在所在顶点的父级。
  • 如果 i- 第一个字符 S is L,转到他现在所在顶点的左子节点。
  • 如果 i- 第一个字符 S is R,转到他现在所在顶点的右子节点。

找到之后高桥将在的顶点的索引 N 移动。在给定的情况下,保证答案最多是 10^{18}.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq X \leq 10^{18}
  • N 和 X 是整数。
  • S 的长度为 N 包括 U, L,和 R.
  • 当 Takahashi 位于根时,他从不尝试去找父级。
  • 当高桥在树叶上时,他从不尝试去找孩子。
  • 顶点 Takahashi 的索引在之后 N 最多移动 10^{18}.

输入

输入由标准输入按以下格式给出:

N X
S

输出

打印答案。


示例输入 1

3 2
URL

示例输出 1

6

完美二叉树具有以下结构。

Figure

三步走,高桥走 2 \to 1 \to 3 \to 6.


示例输入 2

4 500000000000000000
RRUU

示例输出 2

500000000000000000

在此过程中,高桥可能处于索引超过的顶点 10^{18}.


示例输入 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

示例输出 3

126419752371