310649: CF1864I. Future Dominators

I. Future Dominatorstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

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

Output

4 2 3 1 
9 7 6 3 5 8 2 1 4 
1 

Note

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$

题目大意：
Dhruvil 和 amenotiomoi 在线聊天，amenotiomoi 有一个空的 n×n 大小的棋盘，而 Dhruvil 有一个序列整数 1, 2, …, n²，每个数字恰好出现一次。这些数字可以放置在棋盘的单元格中，每个单元格要么为空，要么恰好包含一个数字。

如果剩余的数字可以放置在空单元格中，使得除了数字 1 以外的所有数字都有一个较小值的邻居，则当前棋盘状态被称为“good”。两个单元格相邻如果它们共享一个边缘。

amenotiomoi 向 Dhruvil 发送 q 次查询，每次提供一个空单元格 (x, y)。Dhruvil 必须放置剩余数字中的一个在这个单元格中，使得棋盘仍然是 good 的。在所有可能的方式中，他选择可以放置的最大数字，并将其作为对查询的答案发送给 amenotiomoi。

由于 amenotiomoi 每次都知道正确答案，因此他告诉 Dhruvil (x ⊕ k, y ⊕ k) 而不是 (x, y)，其中 k 是前一个查询的答案。如果 amenotiomoi 发送第一个查询，则他认为 k = 0。Dhruvil 必须每次解码查询并将答案发送给 amenotiomoi。这里的 ⊕ 表示按位异或操作。

帮助 Dhruvil 回复 amenotiomoi 的所有查询。

输入输出数据格式：
每个测试包含多个测试用例。第一行包含测试用例数 t (1 ≤ t ≤ 100)。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 n 和 q (1 ≤ n ≤ 10³, 1 ≤ q ≤ n²)。

接下来的 q 行中的第 i 行包含两个整数 x' 和 y'。对应的单元格是 (x, y)，其中 x' = x ⊕ k 和 y' = y ⊕ k，k 是前一个查询的正确答案。如果 i = 1，则使用 k = 0。保证 1 ≤ x, y ≤ n，并且 (x, y) 在第 i 次查询时是一个空单元格。

保证所有测试用例的 n² 之和不超过 10⁶。

对于每个测试用例，输出一行，包含对所有查询的答案，答案之间由空格分隔。题目大意： Dhruvil 和 amenotiomoi 在线聊天，amenotiomoi 有一个空的 n×n 大小的棋盘，而 Dhruvil 有一个序列整数 1, 2, …, n²，每个数字恰好出现一次。这些数字可以放置在棋盘的单元格中，每个单元格要么为空，要么恰好包含一个数字。 如果剩余的数字可以放置在空单元格中，使得除了数字 1 以外的所有数字都有一个较小值的邻居，则当前棋盘状态被称为“good”。两个单元格相邻如果它们共享一个边缘。 amenotiomoi 向 Dhruvil 发送 q 次查询，每次提供一个空单元格 (x, y)。Dhruvil 必须放置剩余数字中的一个在这个单元格中，使得棋盘仍然是 good 的。在所有可能的方式中，他选择可以放置的最大数字，并将其作为对查询的答案发送给 amenotiomoi。 由于 amenotiomoi 每次都知道正确答案，因此他告诉 Dhruvil (x ⊕ k, y ⊕ k) 而不是 (x, y)，其中 k 是前一个查询的答案。如果 amenotiomoi 发送第一个查询，则他认为 k = 0。Dhruvil 必须每次解码查询并将答案发送给 amenotiomoi。这里的 ⊕ 表示按位异或操作。 帮助 Dhruvil 回复 amenotiomoi 的所有查询。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含测试用例数 t (1 ≤ t ≤ 100)。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 n 和 q (1 ≤ n ≤ 10³, 1 ≤ q ≤ n²)。 接下来的 q 行中的第 i 行包含两个整数 x' 和 y'。对应的单元格是 (x, y)，其中 x' = x ⊕ k 和 y' = y ⊕ k，k 是前一个查询的正确答案。如果 i = 1，则使用 k = 0。保证 1 ≤ x, y ≤ n，并且 (x, y) 在第 i 次查询时是一个空单元格。 保证所有测试用例的 n² 之和不超过 10⁶。 对于每个测试用例，输出一行，包含对所有查询的答案，答案之间由空格分隔。