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\le i,j\le n-1)$ such that $i\oplus j\in S$, and swap the elements of permutation $p$ at positions $i$ and $j$.

Here, $\oplus$ 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\le i\le 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\le n\le 5\cdot 10^5)$ and $\beta (0\le \beta \le 1)$.

The second line contains $n$ numbers $p_i(0\le p_i<n)$ — the starting permutation.

The third line contains one number $q(0\le q\le 5\cdot 10^5)$ — the number of queries.

In the following $q$ lines, two numbers $a_i^{\prime },b_i^{\prime }(0\le a_i^{\prime },b_i^{\prime }\le 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^{\prime }+last\cdot \beta )\mathrm{mod}n$, and $b_i=(b_i^{\prime }+last\cdot \beta )\mathrm{mod}n$.

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:

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

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

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

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

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

Scoring

1. ($8$ points): $n\le 8,\beta =0$;

2. ($10$ points): $n\le 32,q=0,\beta =0$;

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

4. ($25$ points): $n\cdot q\le 9\cdot 10^6,\beta =0$;

5. ($22$ points): $q\le 10^4$;

6. ($45$ points): $\beta =0$;

7. ($150$ points): no additional restrictions.