时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在视频编码中，往往需要将一帧画面分块。 为了简化问题，我们考虑将一幅图片看作 \(2^n×2^n\) 的网格。为了对图片进行处理，编 码器往往会遍历每个格子，但遍历格子的方式在不同的应用中是不同的。 其中一种方式叫做光栅遍历，就是按照从左到右，从上到下的顺序依次进行标号。

　　另一种方式叫做 Z 字型遍历。 可以构造性的给出描述：
　　1. 对于 \(2^0×2^0\) 的网格，直接遍历
　　2. 对于 \(2^k×2^k(k>0)\) 的网格，将其横着从中间、竖着从中间各分成两半，形成 4 个 \(2^(k-1)×2^(k-1)\) 的方格，这四个方格按照左上、右上、左下、右下的顺序依次遍历。

下图是 \(n=3\) 时，\(8×8\) 的网格的两种遍历情况：

【输入格式】

　　输入的第一行为两个整数 \(n,m\)，\(2^n\) 为矩形的边长，\(m\) 为询问次数。
　　接下来 \(m\) 行，每行是一个询问，询每个询问给出一个方格，方式有两种，如下：
　　　　Z x 给出 Z 字形遍历中标号是 x 的方格。
　　　　R x 给出光栅遍历中标号是 x 的方格。 保证存在标号为 x 的方格。

【输出格式】

　　对于每种询问，请输出一行一个正整数，表示在另一种遍历方式中，给出格子的 标号。

【输入输出样例1】

　Input

3 2
Z 37
R 37

　Output

35
49

【子任务】

【来源】

　　Mr.he