Gözəllik Permutasiya Sorğuları

Problem 0-indeksli hesablamadan istifadə edir, yəni, massivlər 0-dan başlayaraq nömrələnir.

$n$ uzunluğunda bir permutasiya, hər bir elementin dəqiq bir dəfə göründüyü və $0$-dan $n-1$-ə qədər olan hər bir ədədin mövcud olduğu müsbət tam ədədlərdən ibarət bir massivdir. Məsələn, $[0]$, $[0,2,1]$, $[0,3,1,2]$ permutasiyalardır, $[0,1,3]$, $[1]$, $[0,1,0]$ isə deyil.

Biz permutasiya $p$-nin çata bilən transformasiyalar dəstini dset $S$-ə görə aşağıdakı əməliyyatı istənilən sayda (0 ola bilər) tətbiq etməklə əldə edilə bilən permutasiyaların dəsti kimi müəyyən edirik:

• İki indeks $i,j(0\le i,j\le n-1)$ seçin ki, $i\oplus j\in S$ olsun və permutasiya $p$-nin $i$ və $j$ mövqelərindəki elementləri dəyişdirin.

Burada, $\oplus$ bitwise XOR əməliyyatını ifadə edir.

Dset $S$ permutasiya $p$-yə görə yaxşıdır adlanır əgər permutasiya $p$-nin çata bilən transformasiyalar dəsti kimlik permutasiyasını ehtiva edirsə.

Biz $m$ uzunluğunda bir permutasiyanı kimlik permutasiya adlandırırıq əgər aşağıdakı şərt ödənilirsə: $a_i=i(0\le i\le m-1)$.

Permutasiya $p$-nin gözəlliyi onunla bağlı yaxşı dset $S$-nin minimum ölçüsü kimi müəyyən edilir.

Sizə $n$ uzunluğunda bir permutasiya $p$ verilir. Siz permutasiyanın ilkin gözəlliyini çıxarmalısınız. Sizə $q$ sorğu da verilir. Hər bir sorğu iki ədəd $a,b$-dən ibarətdir. Hər bir sorğudan sonra, $a$ və $b$ mövqelərindəki elementləri dəyişdirməlisiniz. Qeyd edin ki, permutasiya hər bir sorğudan sonra dəyişiklikləri saxlayır. Hər bir sorğuya cavab olaraq, nəticə permutasiyasının gözəlliyini çıxarmalısınız.

Giriş verilənləri

Birinci sətirdə iki ədəd $n(1\le n\le 5\cdot 10^5)$ və $\beta (0\le \beta \le 1)$ var.

İkinci sətirdə $n$ ədəd $p_i(0\le p_i<n)$ — başlanğıc permutasiya.

Üçüncü sətirdə bir ədəd $q(0\le q\le 5\cdot 10^5)$ — sorğuların sayı.

Sonrakı $q$ sətirdə iki ədəd $a_i^{\prime },b_i^{\prime }(0\le a_i^{\prime },b_i^{\prime }\le n-1)$ verilir — $i$-ci sorğunun parametrləri.

$i$-ci sorğunun dəyərləri aşağıdakı kimi müəyyən edilir. $last$ əvvəlki sorğunun cavabı, ya da bu birinci sorğu olarsa, ilkin permutasiyanın gözəlliyi olsun. Onda $a_i=(a_i^{\prime }+last\cdot \beta )\mathrm{mod}n$, və $b_i=(b_i^{\prime }+last\cdot \beta )\mathrm{mod}n$.

Çıxış verilənləri

Birinci sətirdə, ilkin permutasiyanın gözəlliyini çıxarın.

Sonrakı $q$ sətirdə, sorğuların cavablarını çıxarın.

Nümunələr

Qeyd

İkinci sorğudan sonra, permutasiya $[5,2,1,3,4,0,6]$ olur.

$S=\{3,6\}$ olsun. Bu dəstdən istifadə edərək, permutasiyanı kimlik permutasiyasına çevirmək üçün aşağıdakı dəyişiklikləri edə bilərik:

1. $i=0$ və $j=3$ dəyişdirin. Permutasiya $[\text{3},2,1,\text{5},4,0,6]$ olur.

2. $i=3$ və $j=5$ dəyişdirin. Permutasiya $[3,2,1,\text{0},4,\text{5},6]$ olur.

3. $i=1$ və $j=2$ dəyişdirin. Permutasiya $[3,\text{1},\text{2},0,4,5,6]$ olur.

4. $i=0$ və $j=3$ dəyişdirin. Permutasiya $[\text{0},1,2,\text{3},4,5,6]$ olur.

Sübut etmək olar ki, $|S|\le 1$ olan əməliyyatlarla kimlik permutasiyasını əldə etmək mümkün deyil.

Qiymətləndirmə

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

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

3. ($15$ bal): garanti edilir ki, cavab $2$-dən çox olmayacaq, $\beta =0$;

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

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

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

7. ($150$ bal): əlavə məhdudiyyət yoxdur.