Ana are o afacere cu un şir $S$ format din $N$ litere mici, memorate pe poziţiile $0$, $1$, ..., $N-1$. Şirul este considerat circular (adică după litera de pe poziţia $N-1$ se consideră că urmează litera de pe poziţia $0$).
Asupra acestui şir Ana trebuie să efectueze eficient următoarele operaţii:

* 1. Update( $poz$, $c$): schimbă litera de pe poziţia poz din şir în litera $c$
* 2. Query( $poz1$, $poz2$, $len$): consideră subsecvenţa din şir care începe pe poziţia $poz1$ şi subsecvenţa care începe pe poziţia $poz2$, ambele secvenţe având lungimea $len$, şi determină distanţa $Hamming$ dintre cele două subsecvenţe.

# Update( $poz$, $c$): schimbă litera de pe poziţia poz din şir în litera $c$
# Query( $poz1$, $poz2$, $len$): consideră subsecvenţa din şir care începe pe poziţia $poz1$ şi subsecvenţa care începe pe poziţia $poz2$, ambele secvenţe având lungimea $len$, şi determină distanţa $Hamming$ dintre cele două subsecvenţe.

Distanţa Hamming dintre două subsecvenţe $s1$ şi $s2$ de lungime len este definită ca numărul de poziţii $i$ pentru care $s1[i] ≠ s2[i]$, $0 &le; i < len$.
Pentru că volumul datelor de intrare este mare, vom genera operaţiile asupra şirului pe baza unor valori date, după cum urmează:

h2. Date de intrare

Fişierul de intrare $afaceri.in$ va conţine pe prima linie numerele naturale $N, M, Q, L, A0, A1, A2$ şi $R$. A doua linie va conţine numărul natural $LX$, apoi vor urma $LX$ numere naturale $X{~0~} X{~1~} ... X{~LX-1~}$ reprezentând valorile vectorului $X$. A treia linie va conţine numărul natural $LY$, apoi vor urma $LY$ numere naturale $Y0 Y1 ... Y{~LY-1~}$ reprezentând valorile vectorului $Y$. A patra linie va conţine $N$ litere mici reprezentând şirul dat. Valorile numerice aflate pe aceeaşi linie sunt separate prin spaţii.

Fişierul de intrare $afaceri.in$ va conţine pe prima linie numerele naturale $N, M, Q, L, A0, A1, A2$ şi $R$. A doua linie va conţine numărul natural $LX$, apoi vor urma $LX$ numere naturale $X{~0~} X{~1~} ... X{~LX-1~}$ reprezentând valorile vectorului $X$. A treia linie va conţine numărul natural $LY$, apoi vor urma $LY$ numere naturale $Y{~0~} Y{~1~} ... Y{~LY-1~}$ reprezentând valorile vectorului $Y$. A patra linie va conţine $N$ litere mici reprezentând şirul dat. Valorile numerice aflate pe aceeaşi linie sunt separate prin spaţii.

h2. Date de ieşire

* $1 &le; L < N &le; 2000$
* $1 &le; LX, LY &le; 5000$

* $1 ≤ M ≤ 2 000 000$

* $1 ≤ M ≤ 2.000.000$

* $1 ≤ [M/Q] ≤ 20 001$

* $1 ≤ X[i]≤ R ∀ i$
* $1 ≤ Y[i]≤ R ∀ i$
* $1 ≤ A0, A1, A2, R ≤ 1 000 000$

* $1 ≤ X{~i~} ≤ R ∀ i$
* $1 ≤ Y{~i~} ≤ R ∀ i$
* $1 ≤ A0, A1, A2, R ≤ 1.000.000$

h2. Exemplu

3819