{"raw_statement":[{"iden":"statement","content":"_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.\n\nIn the picture you can see a complete binary tree with _n_ = 15.\n\n<center>![image](https://espresso.codeforces.com/7cf45e9d9e44d8d0a3972224b62a35dd86b5f1b3.png)</center>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_.\n\nYou have to write a program that for given _n_ answers _q_ queries to the tree.\n\nEach 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.\n\nFor example, if _u__i_ = 4 and _s__i_ = «_UURL_», then the answer is 10."},{"iden":"input","content":"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.\n\nThe 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_'.\n\nIt is guaranteed that the sum of lengths of _s__i_ (for each _i_ such that 1 ≤ _i_ ≤ _q_) doesn't exceed 105."},{"iden":"output","content":"Print _q_ numbers, _i_\\-th number must be the answer to the _i_\\-th query."},{"iden":"example","content":"Input\n\n15 2\n4\nUURL\n8\nLRLLLLLLLL\n\nOutput\n\n10\n5"}],"translated_statement":[{"iden":"statement","content":"#cf_span[T] 是一个由 #cf_span[n] 个顶点组成的完全二叉树。这意味着恰好有一个顶点是根，每个顶点要么是叶子（没有子节点），要么是内部节点（恰好有两个子节点）。完全二叉树的所有叶子具有相同的深度（到根的距离）。因此，#cf_span[n] 是一个满足 #cf_span[n + 1] 是 #cf_span[2] 的幂的数。\n\n在图中，你可以看到一个包含 #cf_span[n = 15] 的完全二叉树。\n\n顶点按照一种特殊的递归方式编号为 #cf_span[1] 到 #cf_span[n]：我们首先递归地为左子树的所有顶点分配编号（如果当前顶点不是叶子），然后为当前顶点分配编号，最后递归地为右子树的所有顶点分配编号（如果存在）。图中顶点正是按照此算法编号的。显然，对于每个完全二叉树的大小，都存在唯一一种给所有顶点编号的方式。这种编号方式称为 _symmetric_（对称编号）。\n\n你需要编写一个程序，对于给定的 #cf_span[n]，回答 #cf_span[q] 个关于这棵树的查询。\n\n每个查询由一个整数 #cf_span[ui]（#cf_span[1 ≤ ui ≤ n]）和一个字符串 #cf_span[si] 组成，其中 #cf_span[ui] 是起始顶点的编号，#cf_span[si] 表示从该顶点出发的路径。字符串 #cf_span[si] 仅包含字符 '_L_'、'_R_' 和 '_U_'，分别表示移动到左子节点、右子节点和父节点。必须从左到右依次处理 #cf_span[si] 中的字符，且 #cf_span[ui] 是路径的起始顶点。如果无法处理某个字符（例如，试图从叶子节点向左移动），则跳过该字符。答案是路径结束时所在的顶点编号。\n\n例如，若 #cf_span[ui = 4] 且 #cf_span[si = ]«_UURL_»，则答案为 #cf_span[10]。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 1018]，#cf_span[q ≥ 1]）。#cf_span[n] 满足 #cf_span[n + 1] 是 #cf_span[2] 的幂。\n\n接下来的 #cf_span[2q] 行表示查询；每个查询由两行连续的行组成。第一行包含 #cf_span[ui]（#cf_span[1 ≤ ui ≤ n]），第二行包含非空字符串 #cf_span[si]。#cf_span[si] 不包含除 '_L_'、'_R_' 和 '_U_' 以外的任何字符。\n\n保证所有 #cf_span[si] 的长度之和（对每个 #cf_span[i] 满足 #cf_span[1 ≤ i ≤ q]）不超过 #cf_span[105]。\n\n请输出 #cf_span[q] 个数字，第 #cf_span[i] 个数字必须是第 #cf_span[i] 个查询的答案。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[1 ≤ n ≤ 1018]，#cf_span[q ≥ 1]）。#cf_span[n] 满足 #cf_span[n + 1] 是 #cf_span[2] 的幂。接下来的 #cf_span[2q] 行表示查询；每个查询由两行连续的行组成。第一行包含 #cf_span[ui]（#cf_span[1 ≤ ui ≤ n]），第二行包含非空字符串 #cf_span[si]。#cf_span[si] 不包含除 '_L_'、'_R_' 和 '_U_' 以外的任何字符。保证所有 #cf_span[si] 的长度之和（对每个 #cf_span[i] 满足 #cf_span[1 ≤ i ≤ q]）不超过 #cf_span[105]。"},{"iden":"output","content":"请输出 #cf_span[q] 个数字，第 #cf_span[i] 个数字必须是第 #cf_span[i] 个查询的答案。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{N} $ such that $ n + 1 = 2^h $ for some $ h \\in \\mathbb{N} $.  \nLet $ T_n $ be a complete binary tree with $ n $ vertices, numbered in symmetric (in-order) traversal:  \n- For each subtree rooted at $ v $, recursively number the left subtree, then $ v $, then the right subtree.  \n- The root is numbered $ 2^{h-1} $.  \n\nLet $ \\text{parent}(v) $, $ \\text{left}(v) $, $ \\text{right}(v) $ denote the parent, left child, and right child of vertex $ v $, respectively, under the symmetric numbering.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^{18} $, and $ n + 1 $ is a power of 2.  \n2. $ q \\geq 1 $, and the total length of all query strings $ s_i $ is $ \\leq 10^5 $.  \n3. For each query: $ 1 \\leq u_i \\leq n $, and $ s_i \\in \\{ \\text{L}, \\text{R}, \\text{U} \\}^* $.  \n\n**Objective**  \nFor each query $ (u_i, s_i) $, simulate the path starting at vertex $ u_i $, processing each character in $ s_i $ left-to-right:  \n- 'L': move to left child (if exists); else, skip.  \n- 'R': move to right child (if exists); else, skip.  \n- 'U': move to parent (if exists); else, skip.  \n\nOutput the final vertex number after processing $ s_i $.  \n\n**Helper Functions (Implicit)**  \nLet $ h = \\log_2(n+1) $.  \nFor a vertex $ v $ at depth $ d $ (root at depth 0), its position in the in-order traversal determines its children and parent via recursive structure.  \nDefine:  \n- $ \\text{left}(v) $, $ \\text{right}(v) $, $ \\text{parent}(v) $ as functions computable via binary representation and subtree size arithmetic.","simple_statement":null,"has_page_source":false}