CF2093D.Skibidi Table

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 的问题。

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

每组数据的第一行包含一个整数 $n$，描述表格的大小（$1 \le n \le 30$）。

每组数据的第二行包含一个整数 $q$——问题的数量（$1 \le q \le 20\,000$）。

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

• -> x y —— 询问位于第 $x$ 行第 $y$ 列的单元格中的数字（$1 \le x, y \le 2^n$）；
• <- d —— 询问数字 $d$（$1 \le d \le 2^{2n}$）所在的单元格坐标。

保证所有测试用例的 $q$ 之和不超过 $20\,000$。

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

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

翻译由 DeepSeek V3 完成