D1. XOR Sorting (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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$$$.

Output

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.

Example
Input
3
3 0
2 3 4
2 0
1000000000 999999999
6 0
2 5 3 4 1 6
Output
0
1
4
Note

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$$$.