Vadim 喜欢用整数填充方桌。但今天他想出了一个有趣的方法!例如,一个大小为 $$$2 \times 2$$$ 的表,行从上到下编号,列从左到右编号。我们将 $$$1$$$ 放在左上角单元格中,$$$2$$$ 放在右下角单元格中,$$$3$$$ 放在左下角单元格中,$$$4$$$ 放在右上角单元格中。这就是他所需要的乐趣!
对于 Vadim 来说幸运的是,他有一张大小为 $$$2^n \times 2^n$$$ 的桌子。他计划用从 $$$1$$$ 到 $$$2^{2n}$$$ 升序的整数填充它。为了填满这么大的桌子,Vadim 会将其分成 $$$4$$$ 相等的方桌,先填左上的,然后填右下的,再填左下的,最后填右上的。当他填充时,每个较小的表将被分成更小的表,直到达到 $$$2 \times 2$$$ 大小的表,他将按照上述顺序填写。
现在 Vadim 急于开始填写表格,但他有两种类型的 $$$q$$$ 问题:
- $$$x$$$ 行和 $$$y$$$ 列的单元格中的数字是什么;
- 数字 $$$d$$$ 所在的单元格坐标。
输入
每个测试都包含多组输入数据。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10)$$$ — 输入数据的组数。以下几行描述了输入数据集。
每个数据集的第一行有一个整数$$$n$$$,描述表的大小$$$(1 \le n \le 30)$$$。
在每个数据集的第二行,有一个整数$$$q$$$——问题的数量$$$(1 \le q \le 20\,000)$$$。
在每个数据集的以下 $$$q$$$ 行中,问题按以下格式描述:
- -> x y — 单元格中的数字 $$$(1 \le x, y \le 2^n)$$$;
- <- d — 数字 $$$(1 \le d \le 2^{2n})$$$ 所在的单元格坐标。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$20\,000$$$。
输出
在单独的行上输出每个问题的答案。
示例
输入复制
225-> 4 3<- 15<- 4-> 3 1-> 1 318-> 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
注意
这是第一个示例中填充的表格的样子: