← 返回题目列表

Codeforces · 792/D

D. 完全二叉树中的路径

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

T 是由 n 个顶点组成的完全二叉树。这意味着只有一个顶点是根,每个顶点要么是叶子(并且没有子节点),要么是内部节点(并且恰好有两个子节点)。完全二叉树的所有叶子都具有相同的深度(距根的距离)。所以 n 是一个数字,n + 1 是 2 的幂。

在图中你可以看到一个 n = 15 的完全二叉树。

顶点以一种特殊的递归方式从 1 到 n 编号:我们递归地为左子树中的所有顶点(如果当前顶点不是叶子)分配编号,然后为当前顶点分配编号,然后递归地为右子树(如果存在)中的所有顶点分配编号。在图片中,顶点是使用该算法精确编号的。很明显,对于每个大小的完整二叉树,都存在一种为所有顶点提供数字的方法。这种编号方式称为对称。

您必须编写一个程序,针对给定的 n 个答案对树进行 q 个查询。

每个查询由一个整数 ui (1 ≤ ui ≤ n) 和一个字符串 si 组成,其中 ui 是顶点的数量,si 表示从该顶点开始的路径。字符串 si 不包含除 'L'、'R' 和 'U' 以外的任何字符,分别表示遍历到左子节点、右子节点和父节点。考虑到 ui 是路径开始的顶点,来自 si 的字符必须从左到右处理。如果无法处理某个字符(例如,转到叶子的左子节点),则必须跳过它。答案是 si 表示的路径结束的顶点数。

例如,如果 ui = 4 且 si = «UURL»,则答案为 10。

输入

第一行包含两个整数 n 和 q (1 ≤ n ≤ 1018, q ≥ 1)。 n 使得 n + 1 是 2 的幂。

接下来的 2q 行代表查询;每个查询由两个连续的行组成。这两行中的第一行包含 ui (1 ≤ ui ≤ n),第二行包含非空字符串 si。 si 不包含除“L”、“R”和“U”之外的任何字符。

保证 si 的长度总和(对于每个 i,使得 1 ≤ i ≤ q)不超过 105。

输出

打印 q 个数字,第 i 个数字必须是第 i 个查询的答案。

示例

输入 #1

15 2
4
UURL
8
LRLLLLLLLL

输出 #1

10
5