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$）； - `

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

第一个样例的填充表格如下：  翻译由 DeepSeek V3 完成