afaceri

Ana are o afacere cu un şir $S$ format din $N$ litere mici, memorate pe poziţiile $0, 1, \dots, 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(poz_1, poz_2, len)$: consideră subsecvenţa din şir care începe pe poziţia $poz_1$ şi subsecvenţa care începe pe poziţia $poz_2$, ambele secvenţe având lungimea $len$, şi determină distanţa Hamming dintre cele două subsecvenţe.

Distanţa Hamming dintre două subsecvenţe $s_1$ şi $s_2$ de lungime $len$ este definită ca numărul de poziţii $i$ pentru care $s_{1[i]} \neq s_{2[i]}$, $0 \leq i < len$.

Pentru că volumul datelor de intrare este mare, vom genera operaţiile asupra şirului pe baza unor valori date, după cum urmează:
$M$ - numărul total de operaţii;
$Q$ - frecvenţa operaţiilor Update (după fiecare $Q-1$ operaţii Query se execută un Update);

$L \ A_0 \ A_1 \ A_2 \ R$ - valori (iniţial date) în funcţie de care generăm operaţiile.
Vectorii $X$ cu $L_X$ elemente naturale şi respectiv $Y$ cu $L_Y$ elemente naturale conţin valori utilizate de asemenea pentru generarea operaţiilor (vectorii $X$ şi $Y$ fiind indexaţi de la $0$).
Pseudocodul care descrie modul de generare a operaţiilor Update/Query:

for (i = 1; i <= M; i++)
    {if (i % Q == 0) // generez o operatie Update
         {poz=A1%N; c='a' + A2 % 26;	    
          S[poz] = c; }
	    else //generez o operatie Query
          { poz1 = A0%N; poz2=A1%N; len=L+A2%(N-L+1); }
      //recalculez A0 A1 A2 	     
      VAL = ((long long)A2*X[i%LX]+Y[i%LY])%R; A0 = A1; A1 = A2; A2 = VAL; 
    }

Cerinţă

Scrieţi un program care să efectueze operaţiile generate şi să determine suma răspunsurilor la operaţiile Query.

Date de intrare

Fişierul de intrare afaceri.in va conţine pe prima linie numerele naturale $N, M, Q, L, A_0, A_1, A_2$ şi $R$. A doua linie va conţine numărul natural $L_X$, apoi vor urma $L_X$ numere naturale $X_0 \ X_1 \dots X_{L_X-1}$ reprezentând valorile vectorului $X$. A treia linie va conţine numărul natural $L_Y$, apoi vor urma $L_Y$ numere naturale $Y_0 \ Y_1 \dots Y_{L_Y-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.

Date de ieșire

Fişierul de ieşire afaceri.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând suma răspunsurilor la query-urile date.

Restricții și precizări

• $1 \leq L < N \leq 2 \ 000$;
• $1 \leq L_X, L_Y \leq 5 \ 000$;
• $1 \leq M \leq 2 \ 000 \ 000$;
• $1 \leq \frac{M}{Q} \leq 20 \ 001$
• $1 \leq X_i \leq R, 1 \leq Y_i \leq R, \forall i$
• $1 \leq A_0, A_1, A_2, R \leq 1 \ 000 \ 000$;

Exemplu

afaceri.in

7 15 4 3 5 6 7 8
3 5 4 1
3 7 2 6
lrqagor

afaceri.out

65