You are considering a permutation of
to
and a non-negative integer
. The elements at indices
and
may be swapped only if
where
denotes the XOR of
and
. However,
has not yet been decided. What is the smallest possible non-negative integer
so that this permutation may be sorted from least to greatest?
To make this more interesting, the permutation will be updated. You are given updates of the form
u v
meaning that and
have been swapped. After each of the
updates, what is the best
?
Note that the indices are 1-indexed, but the values are from to
.
Constraints
For all ,
.
is a permutation, so each element from
to
will appear exactly once.
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [30%]
Subtask 4 [20%]
Input Specification
The first line will contain two space-separated integers, and
.
The next line will contain space-separated integers,
.
The following lines will each contain two space-separated integers,
and
, the indices to be swapped.
Output Specification
For each query, output a line containing a single non-negative integer, the smallest possible 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 . Swap
and
, then
and
.
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
Comments