Fişierul intrare/ieşire:	afaceri.in, afaceri.out	Sursă	Lot Iasi 2008, Baraj 5
Autor	Adrian Airinei	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	1.25 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Afaceri

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.

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 ≤ 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 A0 A1 A2 R – valori (iniţial date) în funcţie de care generăm operaţiile.
• Vectorii X cu LX elemente naturale şi respectiv Y cu LY 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, A0, A1, A2 şi R. A doua linie va conţine numărul natural LX, apoi vor urma LX numere naturale X₀ X₁ ... 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₀ Y₁ ... 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.

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

• 1 ≤ L < N ≤ 2000
• 1 ≤ LX, LY ≤ 5000
• 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

Exemplu

Cum se trimit solutii?