Sličnost

문제

Ona je nosila u rukama odvratno, uznemiravajuće žuto cvijeće. Ipak, svidjela mu se.

Prema poznatom teoremu, osobnost svake osobe može se prikazati permutacijom duljine $NN$. Tako se i osobnost našeg junaka, Majstora, može prikazati permutacijom $pp$. A osobnost Margarite, dame koja mu je zapala za oko, može se prikazati permutacijom $qq$.

Mjerilo za sličnost permutacija, a time i sreću u bračnom životu, može se prikazati kao najveća veličina presjeka nekog podintervala duljine $KK$ permutacije $pp$ te podintervala duljine $KK$ permutacije $qq$. Pri tome, presjek se promatra u skupovnom smislu, tj. nije bitan poredak brojeva u podintervalima. Primjerice, u slučaju $N=4N\; =\; 4$, $K=3K\; =\; 3$, sličnost permutacija $(2413)(2\backslash ,4\backslash ,1\backslash ,3)$ te $(1234)(1\backslash ,2\backslash ,3\backslash ,4)$ je $22$ i ona se postiže za bilo koji izbor podintervala.

Otkada je vidio Margaritu, Majstor je opsjednut sličnošću svoje i njezine permutacije, te je njegova osobnost postala veoma promjenjiva. Tako svakog dana, u njegovoj će se permutaciji zamijeniti dva susjedna elementa. Napomenimo da je ta promjena stalna tj. ta dva elementa ostaju zamijenjena tijekom sljedećih dana. Sada ga zanima sličnost njegove i njezine permutacije kad ju je tek ugledao, te sličnost nakon promjene tijekom sljedećih $QQ$ dana. Dodatno, zanima ga i za koliko se parova podintervala postiže tolika sličnost. U svojim ljubavnim jadima, zamolio Vas je za pomoć!

입력

U prvom su retku brojevi $NN$, $KK$ i $QQ$.

U drugom se retku nalazi $NN$ brojeva gdje $ii$-ti označava $p_{i}p\_i$.

U trećem se retku nalazi $NN$ brojeva gdje $jj$-ti označava $q_{j}q\_j$.

U sljedećih $QQ$ redaka nalaze se opisi promjena. U $ii$-tom se retku nalazi broj $t_{i}t\_i$ (1 &le; t_i < N) koji označava da su se u Majstorovoj permutaciji $pp$ zamijenili brojevi na pozicijama $t_{i}t\_i$ i $t_i+1t\_i\; +\; 1$.

출력

U prvi redak potrebno je ispisati početnu sličnost permutacija i broj parova podintervala za koje se ta sličnost postiže.

U sljedećih $QQ$ redaka potrebno je ispisati isto, nakon promjene toga dana.

힌트

Pojašnjenje drugog probnog primjera:

Podintervali duljine tri u prvoj permutaciji su $(241)(2\backslash ,4\backslash ,1)$ i $(413)(4\backslash ,1\backslash ,3)$, a u drugoj $(123)(1\backslash ,2\backslash ,3)$ i $(234)(2\backslash ,3\backslash ,4)$. Za presjeke imamo:

\{2, 4, 1\} &cap; \{1, 2, 3\} = \{1, 2\}, \{2, 4, 1\} &cap; \{2, 3, 4\} = \{2, 4\}, \{4, 1, 3\} &cap; \{1, 2, 3\} = \{1, 3\}, \{4, 1, 3\} &cap; \{2, 3, 4\} = \{3, 4\},

pa vidimo da sličnost iznosi 2 te da se postiže za četiri para podintervala.

2 1 1
1 2
1 2
1

1 2
1 2

4 3 0
2 4 1 3
1 2 3 4

2 4

5 3 3
1 4 3 2 5
4 5 1 2 3
3
1
4

2 5
2 6
3 1
3 1