题目描述

Vadim 喜欢用整数填充正方形表格。但今天他想出了一个有趣的方法！以 $2 \times 2$ 的表格为例，行从上到下编号，列从左到右编号。我们在左上角单元格放置 $1$，右下角放置 $2$，左下角放置 $3$，右上角放置 $4$。这就是他需要的全部乐趣！

幸运的是，Vadim 有一个大小为 $2^n \times 2^n$ 的表格。他计划用 $1$ 到 $2^{2n}$ 的整数按升序填充它。为了填充这么大的表格，Vadim 会将其分成 $4$ 个相等的正方形子表格，先填充左上角的子表格，然后是右下角的子表格，接着是左下角的子表格，最后是右上角的子表格。每个较小的子表格会继续被分割成更小的子表格，直到分割成 $2 \times 2$ 的表格，并按照上述顺序填充。

现在 Vadim 迫不及待要开始填充表格了，但他有 $q$ 个两种类型的问题：

1. 位于第 $x$ 行第 $y$ 列的单元格中的数字是多少；
2. 数字 $d$ 位于哪个单元格坐标中。

请帮助回答 Vadim 的问题。

输入格式

第一行包含一个整数 $n$，描述表格的大小。

第二行包含一个整数 $q$——问题的数量。

接下来的 $q$ 行描述每个问题，格式如下：

• -> x y —— 询问位于第 $x$ 行第 $y$ 列的单元格中的数字；
• <- d —— 询问数字 $d$ 所在的单元格坐标。

输出格式

对每个问题，输出一行答案。

输入输出样例

2
5
-> 4 3
<- 15
<- 4
-> 3 1
-> 1 3

1
8
-> 1 1
-> 1 2
-> 2 1
-> 2 2
<- 1
<- 2
<- 3
<- 4

7
2 3
1 2
9
13

1
4
3
2
1 1
2 2
2 1
1 2

说明/提示

对于$50\%$的数据$1 \le n \le 10$

对于$100\%$的数据$1 \le n \le 30$, $1 \le q \le 20\,000$, $1 \le x, y \le 2^n$, $1 \le d \le 2^{2n}$

第一个样例的填充表格如下：