You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

Vadim 喜欢用整数填充方形桌子，但今天他想出了一个有趣的方式来做这件事！比如我们考虑一个 $2 \times 2$ 的表格，其中行号从上到下，列号从左到右。我们将数字 $1$ 放在左上角单元格，数字 $2$ 放在右下角单元格，数字 $3$ 放在左下角单元格，数字 $4$ 放在右上角单元格。这就是 Vadim 玩得开心的方式！

幸运的是，Vadim 有一个大小为 $2^n \times 2^n$ 的表格。他计划将整数从 $1$ 到 $2^{2n}$ 按升序填充到这个表格中。为了填充这么大的表格，Vadim 会将其分成 $4$ 个相等的子表格，先填充左上角的子表格，然后是右下角的子表格，再填充左下角的子表格，最后填充右上角的子表格。每个子表格会递归地分成更小的子表格，直到达到 $2 \times 2$ 的表格，并按照上述的方式进行填充。

现在，Vadim 想开始填充这个表格，但他有 $q$ 个问题，问题分为两种类型：

• 问题类型 1：给定 $x$ 行 $y$ 列，问该位置的数字是多少；
• 问题类型 2：给定数字 $d$，问该数字的位置是哪个（即，在哪一行哪一列）。

输入

每个测试包含多个数据集。每个数据集的第一行包含一个整数 $t$ $(1 \leq t \leq 10)$ — 数据集的个数。接下来的行描述了数据集的输入数据。

每个数据集的第一行包含一个整数 $n$，表示表格的大小 $(1 \le n \le 30)$。

每个数据集的第二行包含一个整数 $q$ — 问题的个数 $(1 \le q \le 20\,000)$。

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

• -> $x$ $y$ — 问题类型 1：给定 $x$ 行 $y$ 列，问该位置的数字是什么。
• <- $d$ — 问题类型 2：给定数字 $d$，问该数字的位置是哪个。

保证所有数据集的总问题数 $q$ 不超过 $20\,000$。

输出

对于每个问题，输出相应的答案，每个答案占一行。

2
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