CF1864I Future Dominators

### 题目背景： Dhruvil 和 amenotiomoi 正在不同国家线上聊天。 一开始 amenotiomoi 有一个大小为 $n \times n$ 的空白棋盘，而 Dhruvil 有一个整数序列 $1 , 2 , 3 , 4 , … , n^2$ 每个数字只能出现一次。这些数字可以放置在棋盘的单元格中，**每个单元格要么为空，要么包含一个数字。** 如果存在一种方法可以将剩余的数字放置在空单元格中，使得除了 $1$ 以外的所有数字都有一个比它小的相邻数字，则称棋盘的当前状态为 $good$ 。两个单元格如果相邻，则它们共享一个边。 行的编号从上到下从 $1$ 到 $n$，列的编号从左到右从 $1$ 到 $n$ 。第 $x$ 行和第 $y$ 列交叉处的单元格表示为 $(x,y)$。 在交流过程中，amenotiomoi向Dhruvil提出了 $q$ 个查询。每次他给出一个空单元格 $(x,y)$ 。Dhruvil必须将剩下的数字中的放置一个在这个单元格中，以使得棋盘仍然是 $good$ 的。在所有可能的方法中，他选择能够放置的最大数字，并将这个数字作为对查询的答案告诉amenotiomoi。 由于amenotiomoi每次都知道正确的答案，他告诉Dhruvil不是查询 $(x,y)$ ，而是 $(x \oplus k,y \oplus k)$ ，其中 $k$ 是前一个查询的答案。如果amenotiomoi发送的是第一个查询，他将 $k$ 视为 $0$ 。每次Dhruvil都必须解码查询并将答案告诉amenotiomoi。 你的目标就是帮助Dhruvil回复所有amenotiomoi的查询。

每个测试包含多个测试用例。第一行包含测试用例的数量 $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⊕k,y_i'=y_i⊕k$ ， $k$ 是前一个查询的正确答案。如果 $i=1$ ，则使用 $k=0$ 。保证 $1≤x_i,y_i≤n$ ，并且在第 $i$ 次查询时， $(x_i,y_i)$ 是一个空单元格。 保证所有测试用例中 $n^2$ 的总和不超过 $10^6$。

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

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 $