CF1864I.Future Dominators
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Dhruvil and amenotiomoi are sitting in different countries and chatting online. Initially, amenotiomoi has an empty board of size n×n , and Dhruvil has a sequence of integers 1,2,…,n2 , 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⊕k,y⊕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 ⊕ denotes the bitwise XOR operation.
Help Dhruvil reply to all amenotiomoi's queries.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤100 ). The description of the test cases follows.
The first line of each test case contains two integers n and q ( 1≤n≤103 , 1≤q≤n2 ).
The i -th of the following q lines contains two integers xi′ and yi′ . The corresponding cell is (xi,yi) , where xi′=xi⊕k and yi′=yi⊕k , where k is the correct answer for the previous query. If i=1 , then k=0 is used. It is guaranteed that 1≤xi,yi≤n and that (xi,yi) is an empty cell at the moment of i -th query.
It is guaranteed that the sum of n2 over all test cases does not exceed 106 .
输出格式
For each test case, output one line, containing the answers to all queries, separated by spaces.
输入输出样例
输入#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
说明/提示
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⊕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⊕2=3 , 2⊕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⊕3=1 , 1⊕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