Dhruvil 和 amenotiomoi 坐在不同的国家并在线聊天。最初,amenotiomoi 有一个大小为 $$$n \times n$$$ 的空棋盘,而 Dhruvil 有一个整数序列 $$$1, 2, \ldots, n^2$$$,每个数字只出现一次。这些数字可以放置在棋盘的单元格中,每个单元格要么是空的,要么只包含一个数字。
如果有一种方法可以将剩余的数字放入空单元格中,以便除 $$$1$$$ 之外的所有数字都有一个具有较小值的邻居,则棋盘的当前状态称为良好。如果两个单元共享一条边,则它们是邻居。
行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。
为了聊天,amenotiomoi 向 Dhruvil 询问 $$$q$$$ 问题。每次他都会为 Dhruvil 提供一个空单元格 $$$(x, y)$$$。 Dhruvil 必须将剩余的数字之一放入该单元格中,以便棋盘仍然完好。在执行此操作的所有方法中,他选择他可以放置的最大可能数字,并将该数字发送给 amenotiomoi 作为查询的答案。
由于 amenotiomoi 每次都知道正确答案,他告诉 Dhruvil $$$(x \oplus k,y \oplus k)$$$ 而不是 $$$(x, y)$$$,其中 $$$k$$$ 是上一个查询的答案。如果 amenotiomoi 发送第一个查询,他认为 $$$k = 0$$$。每次 Dhruvil 都必须解码查询并将答案发送给 amenotiomoi。这里$$$\oplus$$$表示按位异或运算。
帮助 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 \oplus k$$$ 和 $$$y_i' = y_i \oplus k$$$,其中 $$$k$$$ 是上一个查询的正确答案。如果 $$$i = 1$$$,则使用 $$$k = 0$$$。保证 $$$1 \le x_i, y_i \le n$$$ 并且 $$$(x_i, y_i)$$$ 在第 $$$i$$$ 查询时是一个空单元格。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一行,包含所有查询的答案,以空格分隔。
示例
输入 #1
3 2 4 1 1 6 6 3 0 1 2 3 9 2 1 8 11 4 4 4 4 2 0 4 4 11 10 1 3 3 2 1 1 1 1
输出 #1
4 2 3 1 9 7 6 3 5 8 2 1 4 1
注意
在第一个测试用例中,第一个查询是 $$$(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$$$