题目背景

搬运自 Code+ 第 6 次网络赛。

题目描述

在视频编码中，往往需要将一帧画面分块。

为了简化问题，我们考虑将一幅图片看作 $2^n\times 2^n$ 的网格。为了对图片进行处理，编码器往往会遍历每个格子，但遍历格子的方式在不同的应用中是不同的。

其中一种方式叫做光栅遍历，就是按照从左到右，从上到下的顺序依次进行标号。下图是一个 $8\times 8$ 的例子：

另一种方式叫做 Z 字型遍历。先看一个 $8\times 8$ 的例子：

可以构造性的给出描述：

1.对于 $2^0\times2^0$ 的网格，直接遍历；

2.对于 $2^k\times2^k(k>0)$ 的网格，将其横着从中间、竖着从中间各分成两半，形成 $4$ 个 $2^{k-1}\times2^{k-1}$ 的方格，这四个方格按照左上、右上、左下、右下的顺序依次遍历。

输入格式

输入的第一行为两个整数 $n,m$，其中 $2^n$ 为矩形的边长，$m$ 为询问次数。

接下来 $m$ 行，每行是一个询问，每个询问给出一个方格，方式有两种，如下：

• Z x：给出 Z 字形遍历中标号是 $x$ 的方格。
• R x：给出光栅遍历中标号是 $x$ 的方格。

保证存在标号为 $x$ 的方格。

输出格式

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

3 2
Z 37
R 37

35
49

提示

样例解释

如上图所示。

数据范围

对于所有数据，保证 $1\le n\le 30$，$1\le m\le 5\times10^5$。