You are considering a permutation $P$ of $0$ to $N-1$ and a non-negative integer $C$. The elements at indices $i$ and $j$ may be swapped only if $P_i\oplus P_j\le C$ where $A\oplus B$ denotes the XOR of $A$ and $B$. However, $C$ has not yet been decided. What is the smallest possible non-negative integer $C$ so that this permutation may be sorted from least to greatest?

To make this more interesting, the permutation will be updated. You are given $Q$ updates of the form u v meaning that $P_u$ and $P_v$ have been swapped. After each of the $Q$ updates, what is the best $C$?

Note that the indices are 1-indexed, but the values are from $0$ to $N-1$.

Constraints

For all $1\le i\le N$, $0\le P_i\le N-1$.
$P$ is a permutation, so each element from $0$ to $N-1$ will appear exactly once.
$1\le u,v\le N$

Subtask 1 [20%]

$1\le N\le 400$
$1\le Q\le 400$

Subtask 2 [30%]

$1\le N\le 200000$
$Q=1$

Subtask 3 [30%]

$1\le N\le 50000$
$1\le Q\le 50000$

Subtask 4 [20%]

$1\le N\le 200000$
$1\le Q\le 200000$

Input Specification

The first line will contain two space-separated integers, $N$ and $Q$.
The next line will contain $N$ space-separated integers, $P_1,P_2,\dots ,P_N$.
The following $Q$ lines will each contain two space-separated integers, $u$ and $v$, the indices to be swapped.

Output Specification

For each query, output a line containing a single non-negative integer, the smallest possible $C$ given the current permutation.

Sample Input 1

4 2
2 3 1 0
4 3
1 1

Sample Output 1

2
2

Explanation for Sample 1

After the first update, the permutation is $2,3,0,1$. Swap $2$ and $0$, then $3$ and $1$.
The second update doesn't change anything.

Sample Input 2

4 3
1 0 2 3
1 2
3 4
1 4

Sample Output 2

0
1
2