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 .
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%]
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.
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
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