CF2247D1.XOR Sorting (Easy Version)

This is the easy version of the problem. The only difference between the versions is that in this version, $q = 0$.

Note that zero-based indexing is used in this problem.

For an array $b$ consisting of $m$ positive integers, define $f(b)$ as follows.

For a non-negative integer $k$, we say that $b$ can be $k$-sorted if it can be sorted in non-decreasing order by performing the following operation any number of times:

1. Choose two indices $i$ and $j$ ($0 \le i \lt j \le m - 1$) such that $i \oplus j \le k$$^{\text{∗}}$. Note that the condition applies to the indices $i$ and $j$, not to the elements $b_i$ and $b_j$.
2. Swap the elements $b_i$ and $b_j$.

The value $f(b)$ is defined as the smallest non-negative integer $k$ such that the array $b$ can be $k$-sorted.

You are given an array $a$ of length $n$, consisting of positive integers. You will perform $q$ updates on $a$. Each update has the following form:

• $i \; x$: assign $a_i = x$.

Note that the updates are persistent. In other words, each update affects all subsequent states of the array.

For each of the $q + 1$ states of $a$ — the initial state and the state after each of the $q$ updates — find the value of $f(a)$.

$^{\text{∗}}$$\oplus$ denotes the bitwise XOR operation

这是该问题的简单版本。两个版本的唯一区别在于本版本中 $q = 0$。

注意：本题中采用从 0 开始的索引。

对于一个由 $m$ 个正整数组成的数组 $b$，定义函数 $f(b)$ 如下：

对于一个非负整数 $k$，若可通过执行以下操作任意多次将 $b$ 排序为非递减顺序，则称 $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)$ 定义为使得数组 $b$ 可被 $k$-排序的最小非负整数 $k$。

你被给定一个长度为 $n$ 的正整数数组 $a$。你将对 $a$ 执行 $q$ 次更新操作。每次更新的形式如下：

• $i \; x$：令 $a_i = x$。

注意：这些更新是持久化的。换言之，每次更新都会影响数组后续的所有状态。

对于 $a$ 的 $q + 1$ 个状态（即初始状态，以及每次更新后的状态），请分别求出 $f(a)$ 的值。

$^{\text{∗}}$$\oplus$ 表示 按位异或运算

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). 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^6, q = 0$) — the length of the array $a$ and the number of updates.

The second line of each test case contains $n$ integers $a_0, a_1, \ldots, a_{n - 1}$ ($1 \le a_i \le 10^9$) — the array $a$.

The $j$-th of the following $q$ lines contains two integers $i_j$ and $x_j$ ($0 \le i_j \lt n$, $1 \le x_j \le 10^9$) — the description of the $j$-th update. This update means that the assignment $a_{i_j} = x_j$ is performed.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

接下来的 $q$ 行中，第 $j$ 行包含两个整数 $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$。

For each test case, output $q + 1$ integers — the values of $f(a)$ for the initial state of the array and after each of the $q$ updates, in order.

对于每个测试用例，输出 $q + 1$ 个整数——即数组初始状态下的 $f(a)$ 值，以及每次 $q$ 次更新后的 $f(a)$ 值（按顺序）。

In the first example, the array is $a = [2, 3, 4]$. It is already sorted, so $f(a) = 0$.

In the second example, the array is $a = [10^9, 10^9 - 1]$. We can swap $a_0$ and $a_1$, transforming $a$ as follows: $[\color{red}{10^9}, \color{red}{10^9 - 1}] \rightarrow [\color{red}{10^9 - 1}, \color{red}{10^9}]$. Therefore, $f(a) = 0 \oplus 1 = 1$.

In the third example, the array is $a = [2, 5, 3, 4, 1, 6]$. We can perform swaps using the index pairs $(0, 1)$ and $(0, 4)$, transforming $a$ as follows: $[\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]$. It can be shown that no smaller value of $k$ is sufficient, so $f(a) = \max(0 \oplus 1, 0 \oplus 4) = 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$。