CF792D.Paths in a Complete Binary Tree

T is a complete binary tree consisting of n vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn't have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So n is a number such that n + 1 is a power of 2.

In the picture you can see a complete binary tree with n = 15.

Vertices are numbered from 1 to n in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.

You have to write a program that for given n answers q queries to the tree.

Each query consists of an integer number u__i (1 ≤ u__i ≤ n) and a string s__i, where u__i is the number of vertex, and s__i represents the path starting from this vertex. String s__i doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from s__i have to be processed from left to right, considering that u__i is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by s__i ends.

For example, if u__i = 4 and s__i = «UURL», then the answer is 10.

$T$ 是一棵包含 $n$ 个顶点的完全二叉树。这意味着：恰好存在一个根节点，且每个顶点要么是叶子节点（没有子节点），要么是内部节点（恰好有两个子节点）。完全二叉树的所有叶子节点具有相同的深度（即到根节点的距离）。因此，$n$ 是满足 $n + 1$ 为 2 的幂的整数。

下图展示了一棵 $n = 15$ 的完全二叉树。

顶点按一种特殊的递归方式编号，范围为 $1$ 到 $n$：若当前顶点不是叶子节点，则首先递归地为其左子树中所有顶点编号；然后为当前顶点编号；最后递归地为其右子树中所有顶点编号（若右子树存在）。图中顶点的编号正是按照该算法得到的。显然，对于任意给定大小的完全二叉树，顶点编号方式唯一。这种编号方式称为中序编号（symmetric numbering）。

你需要编写一个程序，在给定 $n$ 的前提下，回答 $q$ 个关于该树的查询。

每个查询由一个整数 $u_i$（$1 \le u_i \le n$）和一个字符串 $s_i$ 组成：其中 $u_i$ 表示起始顶点的编号，$s_i$ 表示一条从该顶点出发的路径。字符串 $s_i$ 仅包含字符 'L'、'R' 和 'U'，分别表示移动到左子节点、右子节点和父节点。需按从左到右的顺序依次处理 $s_i$ 中的每个字符，起始位置为顶点 $u_i$。若某一步操作无法执行（例如：试图访问叶子节点的左子节点），则跳过该字符。最终答案为路径结束时所在顶点的编号。

例如，若 $u_i = 4$ 且 $s_i = \text{``UURL''}$，则答案为 $10$。

The first line contains two integer numbers n and q (1 ≤ n ≤ 1018, q ≥ 1). n is such that n + 1 is a power of 2.

The next 2_q_ lines represent queries; each query consists of two consecutive lines. The first of these two lines contains u__i (1 ≤ u__i ≤ n), the second contains non-empty string s__i. s__i doesn't contain any characters other than 'L', 'R' and 'U'.

It is guaranteed that the sum of lengths of s__i (for each i such that 1 ≤ i ≤ q) doesn't exceed 105.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^{18}$，$q \geq 1$）。其中 $n$ 满足 $n + 1$ 是 $2$ 的幂。

接下来的 $2q$ 行表示查询；每个查询由连续两行组成。这两行中的第一行包含整数 $u_i$（$1 \leq u_i \leq n$），第二行包含一个非空字符串 $s_i$。字符串 $s_i$ 仅由字符 'L'、'R' 和 'U' 构成。

保证所有 $s_i$（其中 $1 \leq i \leq q$）的长度之和不超过 $10^5$。

Print q numbers, i-th number must be the answer to the i-th query.

输出 q 个数，其中第 i 个数为第 i 个查询的答案。