← 返回题目列表

Codeforces · 2093/D

D. 斯基比迪表

中文机器翻译题面 查看原题

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$$$ 所在的单元格坐标。
Help answer Vadim's questions.

输入

每个测试都包含多组输入数据。第一行包含一个整数 $$$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$$$。

输出

在单独的行上输出每个问题的答案。

示例

输入
复制

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

注意

这是第一个示例中填充的表格的样子: