Запросы на красоты перестановки

В задаче используется 0-индексация, т.е. массивы нумеруются с 0.

Перестановка длины $n$ — это массив положительных целых чисел, где каждый элемент встречается ровно один раз, и каждое число от $0$ до $n-1$ присутствует. Например, $[0]$, $[0,2,1]$, $[0,3,1,2]$ являются перестановками, в то время как $[0,1,3]$, $[1]$, $[0,1,0]$ — нет.

Мы определяем множество достижимых преобразований перестановки $p$ относительно множества $S$ как множество перестановок, которые можно получить из $p$, применяя следующую операцию любое количество раз (возможно, 0):

• Выберите два индекса $i,j(0\le i,j\le n-1)$ такие, что $i\oplus j\in S$, и поменяйте местами элементы перестановки $p$ на позициях $i$ и $j$.

Здесь $\oplus$ обозначает побитовую операцию XOR.

Множество $S$ называется хорошим относительно перестановки $p$, если множество достижимых преобразований перестановки $p$ содержит тождественную перестановку.

Мы называем перестановку $a$ длины $m$ тождественной перестановкой, если выполняется следующее: $a_i=i(0\le i\le m-1)$.

Красота перестановки $p$ определяется как минимальный размер хорошего множества $S$ относительно нее.

Вам дана перестановка $p$ длины $n$. Вам нужно вывести начальную красоту перестановки. Вам также даны $q$ запросов. Каждый запрос состоит из двух чисел $a,b$. После каждого запроса вам нужно поменять местами элементы на позициях $a$ и $b$. Обратите внимание, что перестановка сохраняет изменения после каждого запроса. В ответ на каждый запрос вам нужно вывести красоту полученной перестановки.

Входные данные

Первая строка содержит два числа $n(1\le n\le 5\cdot 10^5)$ и $\beta (0\le \beta \le 1)$.

Вторая строка содержит $n$ чисел $p_i(0\le p_i<n)$ — начальная перестановка.

Третья строка содержит одно число $q(0\le q\le 5\cdot 10^5)$ — количество запросов.

В следующих $q$ строках даны два числа $a_i^{\prime },b_i^{\prime }(0\le a_i^{\prime },b_i^{\prime }\le n-1)$ — параметры $i$-го запроса.

Значения $i$-го запроса определяются следующим образом. Пусть $last$ — это ответ на предыдущий запрос или красота начальной перестановки, если это первый запрос. Тогда $a_i=(a_i^{\prime }+last\cdot \beta )\mathrm{mod}n$, и $b_i=(b_i^{\prime }+last\cdot \beta )\mathrm{mod}n$.

Выходные данные

В первой строке выведите красоту начальной перестановки.

В следующих $q$ строках выведите ответы на запросы.

Примеры

Примечание

После второго запроса перестановка становится $[5,2,1,3,4,0,6]$.

Пусть $S=\{3,6\}$. Используя это множество, мы можем выполнить следующие обмены, чтобы преобразовать перестановку в тождественную перестановку:

1. Поменяйте местами $i=0$ и $j=3$. Перестановка становится $[\text{3},2,1,\text{5},4,0,6]$.

2. Поменяйте местами $i=3$ и $j=5$. Перестановка становится $[3,2,1,\text{0},4,\text{5},6]$.

3. Поменяйте местами $i=1$ и $j=2$. Перестановка становится $[3,\text{1},\text{2},0,4,5,6]$.

4. Поменяйте местами $i=0$ и $j=3$. Перестановка становится $[\text{0},1,2,\text{3},4,5,6]$.

Можно доказать, что невозможно получить тождественную перестановку, выполняя операции с $|S|\le 1$.

Оценивание

1. ($8$ баллов): $n\le 8,\beta =0$;

2. ($10$ баллов): $n\le 32,q=0,\beta =0$;

3. ($15$ баллов): гарантируется, что ответ не превышает $2$, $\beta =0$;

4. ($25$ баллов): $n\cdot q\le 9\cdot 10^6,\beta =0$;

5. ($22$ баллов): $q\le 10^4$;

6. ($45$ баллов): $\beta =0$;

7. ($150$ баллов): без дополнительных ограничений.