D1. XOR-сортировка (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное отличие между версиями заключается в том, что в этой версии $$$q = 0$$$.

Обратите внимание, что в этой задаче используется нулевая индексация.

Для массива $$$b$$$, состоящего из $$$m$$$ положительных целых чисел, определим $$$f(b)$$$ следующим образом.

Для неотрицательного целого числа $$$k$$$ будем говорить, что массив $$$b$$$ можно $$$k$$$-отсортировать, если его можно отсортировать в порядке неубывания, выполняя следующую операцию любое количество раз:

  1. Выбрать два индекса $$$i$$$ и $$$j$$$ ($$$0 \le i \lt j \le m - 1$$$) такие, что $$$i \oplus j \le k$$$$$$^{\text{∗}}$$$. Обратите внимание, что это условие применяется к индексам $$$i$$$ и $$$j$$$, а не к элементам $$$b_i$$$ и $$$b_j$$$.
  2. Поменять местами элементы $$$b_i$$$ и $$$b_j$$$.

Значение $$$f(b)$$$ определяется как наименьшее неотрицательное целое число $$$k$$$, такое что массив $$$b$$$ можно $$$k$$$-отсортировать.

Вам дан массив $$$a$$$ длины $$$n$$$, состоящий из положительных целых чисел. Вам предстоит выполнить $$$q$$$ обновлений массива $$$a$$$. Каждое обновление имеет следующий вид:

  • $$$i \; x$$$: присвоить $$$a_i = x$$$.

Обратите внимание, что обновления являются постоянными. Другими словами, каждое обновление влияет на все последующие состояния массива.

Для каждого из $$$q + 1$$$ состояний массива $$$a$$$ — исходного состояния и состояния после каждого из $$$q$$$ обновлений — найдите значение $$$f(a)$$$.

$$$^{\text{∗}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^6, q = 0$$$) — длина массива $$$a$$$ и количество обновлений.

Во второй строке каждого набора входных данных даны $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^9$$$) — массив $$$a$$$.

В $$$j$$$-й из следующих $$$q$$$ строк даны два целых числа $$$i_j$$$ и $$$x_j$$$ ($$$0 \le i_j \lt n$$$, $$$1 \le x_j \le 10^9$$$) — описание $$$j$$$-го обновления. Это обновление означает, что выполняется присвоение $$$a_{i_j} = x_j$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q + 1$$$ целых чисел — значения $$$f(a)$$$ для исходного состояния массива и после каждого из $$$q$$$ обновлений в порядке их выполнения.

Пример
Входные данные
3
3 0
2 3 4
2 0
1000000000 999999999
6 0
2 5 3 4 1 6
Выходные данные
0
1
4
Примечание

В первом наборе входных данных массив равен $$$a = [2, 3, 4]$$$. Он уже отсортирован, поэтому $$$f(a) = 0$$$.

Во втором наборе входных данных массив равен $$$a = [10^9, 10^9 - 1]$$$. Мы можем поменять местами $$$a_0$$$ и $$$a_1$$$, изменив $$$a$$$ следующим образом: $$$[\color{red}{10^9}, \color{red}{10^9 - 1}] \rightarrow [\color{red}{10^9 - 1}, \color{red}{10^9}]$$$. Следовательно, $$$f(a) = 0 \oplus 1 = 1$$$.

В третьем наборе входных данных массив равен $$$a = [2, 5, 3, 4, 1, 6]$$$. Мы можем выполнить обмены по парам индексов $$$(0, 1)$$$ и $$$(0, 4)$$$, изменив $$$a$$$ следующим образом: $$$[\color{red}{2}, \color{red}{5}, 3, 4, 1, 6] \rightarrow [\color{red}{5}, \color{red}{2}, 3, 4, 1, 6]$$$, $$$[\color{red}{5}, 2, 3, 4, \color{red}{1}, 6] \rightarrow [\color{red}{1}, 2, 3, 4, \color{red}{5}, 6]$$$. Можно показать, что никакого меньшего значения $$$k$$$ недостаточно, поэтому $$$f(a) = \max(0 \oplus 1, 0 \oplus 4) = 4$$$.