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