CF2247D1 XOR Sorting (Easy Version)

这是这个问题的简单版本。简单版与困难版的唯一区别在于，本题中 $q = 0$。 注意：本题采用从零开始的下标。 对于由 $m$ 个正整数构成的数组 $b$，定义 $f(b)$ 如下。 对于一个非负整数 $k$，如果可以通过任意次数以下操作将 $b$ 排成非递减顺序，我们称 $b$ 可以被 $k$-排序： 1. 选择两个下标 $i$ 与 $j$ ($0 \le i < j \le m - 1$)，且满足 $i \oplus j \le k$。注意，这里的条件仅适用于下标 $i$ 和 $j$，而不是元素 $b_i$ 与 $b_j$。 2. 交换元素 $b_i$ 和 $b_j$。 $f(b)$ 被定义为最小的非负整数 $k$，使得该数组 $b$ 可以被 $k$-排序。 给定长度为 $n$ 的正整数数组 $a$。将对 $a$ 进行 $q$ 次更新。每次更新的具体形式如下： - $i \; x$：表示赋值 $a_i = x$。 注意，更新具有持久性。也就是说，每次更新都会影响之后所有数组 $a$ 的状态。 对于 $a$ 的每一个状态——初始状态，以及每一次更新之后的状态——请找到 $f(a)$ 的值。 $^\text{∗}$ 这里的 $\oplus$ 表示[按位异或操作](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每组测试数据包含多个测试用例。第一行是测试用例数 $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$ 行，每行为两个整数 $i_j$ 和 $x_j$，满足 $0 \le i_j < n,~1 \le x_j \le 10^9$，表示将 $a_{i_j}$ 赋值为 $x_j$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。 保证所有测试用例中 $q$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $q + 1$ 个整数，依次表示初始状态和每次更新之后的 $f(a)$。

在第一个示例中，数组 $a = [2,3,4]$ 已经是有序的，因此 $f(a) = 0$。 在第二个示例中，数组 $a = [10^9, 10^9 - 1]$。可以交换 $a_0$ 和 $a_1$，数组变为 $[10^9-1, 10^9]$。因此 $f(a) = 0 \oplus 1 = 1$。 在第三个示例中，数组 $a = [2, 5, 3, 4, 1, 6]$。可以通过下标对 $(0,1)$ 与 $(0,4)$ 进行交换，将数组变为 $[5,2,3,4,1,6]$，再变为 $[1,2,3,4,5,6]$。可以证明没有更小的 $k$ 能满足排序条件，因此 $f(a) = \max(0 \oplus 1, 0 \oplus 4) = 4$。 由 ChatGPT 5 翻译