# Beauty Permutation Queries

The problem uses 0-indexing, i.e., arrays are numbered starting from 0.

A permutation of length $n$ is an array of positive integers where each element appears exactly once and every number from $0$ to $n−1$ is present. For example, $[0]$, $[0,2,1]$, $[0,3,1,2]$ are permutations, while $[0,1,3]$, $[1]$, $[0,1,0]$ are not.

We define the set of reachable transformations of permutation $p$ with respect to set $S$ as the set of permutations that can be obtained from $p$ by applying the following operation any number of times (possibly 0):

Choose two indices $i,j(0≤i,j≤n−1)$ such that $i⊕j∈S$, and swap the elements of permutation $p$ at positions $i$ and $j$.

Here, $⊕$ denotes the bitwise XOR operation.

The set $S$ is called good with respect to permutation $p$ if the set of reachable transformations of permutation $p$ contains an identity permutation.

We call a permutation $a$ of length $m$ identity permutation if the following holds: $a_{i}=i(0≤i≤m−1)$.

The beauty of permutation $p$ is defined as the minimum size of a good set $S$ with respect to it.

You are given a permutation $p$ of length $n$. You need to output the initial beauty of the permutation. You are also given $q$ queries. Each query consists of two numbers $a,b$. After each query, you need to swap the elements at positions $a$ and $b$. Note that the permutation retains changes after each query. In response to each query, you need to output the beauty of the resulting permutation.

## Input

The first line contains two numbers $n(1≤n≤5⋅10_{5})$ and $β(0≤β≤1)$.

The second line contains $n$ numbers $p_{i}(0≤p_{i}<n)$ — the starting permutation.

The third line contains one number $q(0≤q≤5⋅10_{5})$ — the number of queries.

In the following $q$ lines, two numbers $a_{i},b_{i}(0≤a_{i},b_{i}≤n−1)$ are given — the parameters of the $i$-th query.

The values of the $i$-th query are determined as follows. Let $last$ be the answer to the previous query, or the beauty of the initial permutation if this is the first query. Then $a_{i}=(a_{i}+last⋅β)modn$, and $b_{i}=(b_{i}+last⋅β)modn$.

## Output

In the first line, output the beauty of the initial permutation.

In the following $q$ lines, output the answers to the queries.

## Examples

## Note

After the second query, the permutation becomes $[5,2,1,3,4,0,6]$.

Let $S={3,6}$. Using this set, we can perform the following swaps to transform the permutation into the identity permutation:

Swap $i=0$ and $j=3$. The permutation becomes $[3,2,1,5,4,0,6]$.

Swap $i=3$ and $j=5$. The permutation becomes $[3,2,1,0,4,5,6]$.

Swap $i=1$ and $j=2$. The permutation becomes $[3,1,2,0,4,5,6]$.

Swap $i=0$ and $j=3$. The permutation becomes $[0,1,2,3,4,5,6]$.

It can be proven that it's impossible to obtain the identity permutation by performing operations with $∣S∣≤1$.

## Scoring

($8$ points): $n≤8,β=0$;

($10$ points): $n≤32,q=0,β=0$;

($15$ points): it is guaranteed that the answer does not exceed $2$, $β=0$;

($25$ points): $n⋅q≤9⋅10_{6},β=0$;

($22$ points): $q≤10_{4}$;

($45$ points): $β=0$;

($150$ points): no additional restrictions.