CF1864I.Future Dominators

Dhruvil and amenotiomoi are sitting in different countries and chatting online. Initially, amenotiomoi has an empty board of size $n \times n$, and Dhruvil has a sequence of integers $1, 2, \ldots, n^2$, each number occurring exactly once. The numbers may be placed in the cells of the board, each cell is either empty or contains exactly one number.

The current state of the board is called good, if there is a way of placing the remaining numbers in empty cells so that all numbers except $1$ have a neighbor with a smaller value. Two cells are neighbors if they share an edge.

The rows are numbered from $1$ to $n$ from top to bottom, the columns are numbered from $1$ to $n$ from left to right. The cell at the intersection of the $x$-th row and the $y$-th column is denoted as $(x, y)$.

To chat, amenotiomoi asks $q$ queries to Dhruvil. Each time he provides Dhruvil with an empty cell $(x, y)$. Dhruvil has to place one of the remaining numbers in this cell so that the board is still good. Among all ways to do this, he chooses the largest possible number he can place and sends this number to amenotiomoi as the answer to the query.

Since amenotiomoi knows the correct answer every time, he tells Dhruvil $(x \oplus k,y \oplus k)$ instead of $(x, y)$, where $k$ is the answer for the previous query. If amenotiomoi is sending the first query, he considers $k = 0$. Each time Dhruvil has to decode the query and send the answer to amenotiomoi. Here $\oplus$ denotes the bitwise XOR operation.

Help Dhruvil reply to all amenotiomoi's queries.

德鲁维尔和amenotiomoi身处不同国家，正在网上聊天。初始时，amenotiomoi拥有一块大小为 $n \times n$ 的空棋盘，而德鲁维尔持有一个整数序列 $1, 2, \ldots, n^2$，其中每个数字恰好出现一次。这些数字可以被放置在棋盘的格子中，每个格子要么为空，要么恰好包含一个数字。

若存在一种方式，将剩余未放置的数字填入所有空格中，使得除数字 $1$ 外的所有数字均至少有一个邻接格子（即共享一条边的格子）包含比它更小的数值，则称当前棋盘状态为良好（good）。

行号从上到下依次编号为 $1$ 至 $n$，列号从左到右依次编号为 $1$ 至 $n$。第 $x$ 行与第 $y$ 列交叉处的格子记作 $(x, y)$。

为了聊天，amenotiomoi 向德鲁维尔提出 $q$ 个查询。每次他向德鲁维尔提供一个空格子 $(x, y)$。德鲁维尔必须将一个尚未使用的数字放入该格子中，使得棋盘状态仍保持良好。在所有满足条件的填法中，他选择能放入的最大可能数字，并将该数字作为对本次查询的回答发送给 amenotiomoi。

由于 amenotiomoi 每次都已知正确答案，他并不直接告诉德鲁维尔 $(x, y)$，而是发送 $(x \oplus k,\, y \oplus k)$，其中 $k$ 是上一次查询的答案；若这是第一个查询，则令 $k = 0$。每次德鲁维尔都需先解码该查询（即根据收到的坐标和 $k$ 推出真实的 $(x, y)$），再计算并发送答案。此处 $\oplus$ 表示按位异或运算（bitwise XOR）。

请帮助德鲁维尔回答 amenotiomoi 的所有查询。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 10^3$, $1 \le q \le n^2$).

The $i$-th of the following $q$ lines contains two integers $x_i'$ and $y_i'$. The corresponding cell is $(x_i, y_i)$, where $x_i'=x_i \oplus k$ and $y_i' = y_i \oplus k$, where $k$ is the correct answer for the previous query. If $i = 1$, then $k = 0$ is used. It is guaranteed that $1 \le x_i, y_i \le n$ and that $(x_i, y_i)$ is an empty cell at the moment of $i$-th query.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^3$，$1 \le q \le n^2$）。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $x_i'$ 和 $y_i'$。对应的实际格子坐标为 $(x_i, y_i)$，其中 $x_i'=x_i \oplus k$ 且 $y_i' = y_i \oplus k$，而 $k$ 是上一个查询的正确答案；若 $i = 1$（即第一个查询），则取 $k = 0$。保证 $1 \le x_i, y_i \le n$，且在第 $i$ 次查询时格子 $(x_i, y_i)$ 为空。

保证所有测试用例的 $n^2$ 之和不超过 $10^6$。

For each test case, output one line, containing the answers to all queries, separated by spaces.

对于每个测试用例，输出一行，包含所有查询的答案，答案之间用空格分隔。

In the first test case, the first query is $(1, 1)$, Dhruvil puts $4$ in that cell.

The second query is $(6, 6)$, Dhruvil decode it as $(2, 2)$ using the previous answer ($2 \oplus 4 = 6$). If Dhruvil places $3$ to the cell $(2, 2)$, the board stops being good. So, Dhruvil places $2$ in this cell.

The third query is $(3, 0)$, Dhruvil decodes it as $(1, 2)$ using the previous answer ($1 \oplus 2 = 3$, $2 \oplus 2 = 0$). Dhruvil can place $3$ in this cell.

The fourth query is $(1, 2)$, Dhruvil decodes it as $(2, 1)$ using the previous answer ($2 \oplus 3 = 1$, $1 \oplus 3 = 2$). Now, only $1$ remains in the sequence, and after Dhruvil places $1$ in this cell, the board becomes full and remains good.

Here you can see the entire history of the board:

In the second test case, the final state of the board is:

$8$

$7$

$5$

$9$

$3$

$4$

$1$

$2$

$6$

在第一个测试用例中，第一个查询为 $(1, 1)$，Dhruvil 将 $4$ 放入该格子。

第二个查询为 $(6, 6)$，Dhruvil 利用上一次的答案将其解码为 $(2, 2)$（因为 $2 \oplus 4 = 6$）。若 Dhruvil 将 $3$ 放入格子 $(2, 2)$，棋盘将不再满足“好”的条件。因此，Dhruvil 在该格子中放入 $2$。

第三个查询为 $(3, 0)$，Dhruvil 利用上一次的答案将其解码为 $(1, 2)$（因为 $1 \oplus 2 = 3$，$2 \oplus 2 = 0$）。Dhruvil 可以在该格子中放入 $3$。

第四个查询为 $(1, 2)$，Dhruvil 利用上一次的答案将其解码为 $(2, 1)$（因为 $2 \oplus 3 = 1$，$1 \oplus 3 = 2$）。此时序列中仅剩 $1$，Dhruvil 将 $1$ 放入该格子后，棋盘被填满且仍保持“好”的性质。

以下是棋盘的完整演变过程：

在第二个测试用例中，棋盘的最终状态为：

$8$

$7$

$5$

$9$

$3$

$4$

$1$

$2$

$6$