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

У задачі масиви нумеруються з 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$ балів): без додаткових обмежень.