题目描述

给定一棵拥有 $n$ 个节点的满二叉树，第 $i$ 个节点的编号为对这棵满二叉树做中序遍历的时间戳。

共 $q$ 次询问，每次询问给定一个数 $x$ 与一个字符串。字符串中的第 $i$ 位若为 $U$，表示 $x$ 要变成 $x$ 的父节点的编号；若为 $L$，则表示 $x$ 要变成其左孩子的编号；若为 $R$，表示 $x$ 要变成其右孩子的编号。如果某个字符不合法（比如当前 $x$ 为一个叶节点的编号，而这个字符却是 $L$ 或 $R$），就跳过这个操作。

求经过所有操作后，$x$ 的值是多少。

输入格式

第一行两个整数 $n,q$，$n\le 10^{18}$。

接下来 $2q$ 行，每两行表示一个询问。

保证所有询问中，字符串长度总和不超过 $10^5$。

输出格式

对于每次询问，在一行中输出一个整数表示答案。

15 2
4
UURL
8
LRLLLLLLLL

10
5