← 返回题目列表

Codeforces · 1864/I

I. 未来的统治者

中文机器翻译题面 查看原题

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$$$