This is the hard version of the problem. The only difference between the versions is that in this version, $$$0 \le q \le 10^6$$$.

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:

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$$$.
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$$$, $$$0 \le q \le 10^6$$$) — 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.

Note

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

In the second example, the initial 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$$$.

After the only update, the array becomes $$$a = [10^9, 10^9]$$$. It is already sorted, so $$$f(a) = 0$$$.

In the third example, the initial 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$$$.

XOR Sorting (Hard Version)

Examples