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:

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