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:

# 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.

* 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.

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ă:

* $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 ≤ A0, A1, A2, R ≤ 1 000 000$

h2. Exemplu

3819