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$$$).
В $$$i$$$-й из следующих $$$q$$$ строк содержится два целых числа $$$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$$$.
Для каждого набора входных данных, выведите ответы на все запросы через пробел на одной строке.
32 41 16 63 01 23 92 18 114 44 42 04 411 101 33 21 11 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$$$, и если поместить $$$1$$$ в эту клетку, доска останется хорошей.
Ниже представлено история всех изменений доски:
Во втором наборе входных данных итоговое состояние доски выглядит так:
| $$$8$$$ | $$$7$$$ | $$$5$$$ |
| $$$9$$$ | $$$3$$$ | $$$4$$$ |
| $$$1$$$ | $$$2$$$ | $$$6$$$ |
