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

Вхідні дані

Перший рядок містить два числа $n$ ( $1 \leq n \leq 5 \cdot 1 0^{5}$ 1 \le n \le 5 \cdot 10^5) та $β$ ( $0 \leq β \leq 1$ 0 \le \beta \le 1).

Другий рядок містить $n$ чисел $p_{i}$ p_i ( $0 \leq p_{i} < n$ 0 \le p_i < n) — початкова перестановка.

Третій рядок містить одне число $q$ ( $0 \leq q \leq 5 \cdot 1 0^{5}$ 0 \le q \le 5 \cdot 10^5) — кількість запитів.

У наступних $q$ рядках наводяться два числа $a_{i}^{'}, b_{i}^{'}$ a_i', b_i' ( $0 \leq a_{i}^{'}, b_{i}^{'} \leq n - 1$ 0 \le a_i', b_i' \le n - 1) — параметри $i$ -го запиту.

Значення $i$ -го запиту визначаються наступним чином. Нехай $l a s t$ — це відповідь на попередній запит або краса початкової перестановки, якщо це перший запит. Тоді:

a_{i} = (a_{i}^{'} + l a s t \cdot β) mod n, b_{i} = (b_{i}^{'} + l a s t \cdot β) mod n

a_i = (a_i' + last \cdot \beta) \bmod n,\quad b_i = (b_i' + last \cdot \beta) \bmod n

Вихідні дані

У першому рядку виведіть красу початкової перестановки.

У наступних $q$ рядках виведіть відповіді на запити.

Приклади

Приклад

Loading

Примітка

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

Нехай $S = {3, 6}$ S = \{3, 6\}. Використовуючи цю множину, ми можемо виконати наступні обміни, щоб перетворити перестановку в тотожну перестановку:

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

Можна довести, що неможливо отримати тотожну перестановку, виконуючи операції з $∣ S ∣ \leq 1$ |S| \le 1.

Оцінювання

( $8$ балів): $n \leq 8$ n \le 8, $β = 0$ \beta = 0;
( $10$ балів): $n \leq 32$ n \le 32, $q = 0$ q = 0, $β = 0$ \beta = 0;
( $15$ балів): гарантовано, що відповідь не перевищує $2$ , $β = 0$ \beta = 0;
( $25$ балів): $n \cdot q \leq 9 \cdot 1 0^{6}$ n \cdot q \le 9 \cdot 10^6, $β = 0$ \beta = 0;
( $22$ балів): $q \leq 1 0^{4}$ q \le 10^4;
( $45$ балів): $β = 0$ \beta = 0;
( $150$ балів): без додаткових обмежень.