Fișierul intrare/ieșire	ants.in, ants.out	Sursă	Concurs Shumen seniori 2014
Autor	Georgi Georgiev | Yordan Chaparov	Adăugată de	Ionescu Teodor • teoionescu
Timp de execuție pe test	1 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ants

Țara furnicilor continuă să se extindă. Extinderea se face în următorul mod: când un oraș de furnici este suprapopulat, un număr de locuitori ai săi pleacă și întemeiază un nou oraș (de fiecare dată când furnicile se mută, vor rămâne câteva și în orașul vechi). Inițial, țara furnicilor are un singur oraș. Din timpuri străvechi, furnicile au stabilit că în fiecare oraș vor fi exact M mușuroaie, numerotate cu întregi de la 1 la M, și pentru fiecare mușuroi știm câte furnici locuiesc în el. Când se întemeiază un nou oraș, M mușuroaie se construiesc imediat. Pentru că furnicile își respectă tradițiile, ele au o înclinație naturală să își construiască mușuroaiele în orașul nou într-un mod care seamănă cu mușuroaiele din orașul din care s-au mutat. Adică, mușuroiul 1 din noul oraș va avea aceeași capacitate ca mușuroiul 1 din vechiul oraș, mușuroiul 2 din noul oraș – la fel ca mușuroiul 2 din vechiul oraș etc. Pe de altă parte, există furnici inovatoare care vor să facă anumite schimbări în planul noului oraș. Decizia, care a fost deja luată, este că la momentul întemeierii noului oraș, căpetenia furnicilor să dea ordin ca toate capacitățile musuroaielor numerotate de la L la R inclusiv, să fie mărite cu aceeași valoare V.
După ce au fost construite mușuroaiele din noul oraș, considerăm “cartierul select” al orașului acele mușuroaie numerotate de la i la j inclusiv. Acum, căpetenia furnicilor se întreabă câte furnici pot fi găzduite în cartierul select din orașul nou.
Scrieți un program care răspunde la această întrebare pe măsură ce noi orașe se întemeiază.

Date de intrare

Pe prima linie din fișierul de intrare ants.in se găsesc doi întregi: N – numărul de orașe din țara furnicilor după ce toate orașele noi au fost întemeiate și M – numărul de mușuroaie din fiecare oraș.
Pe a două linie se găsesc M întregi A₁, A₂, A₃, …, A_M, unde A_i reprezintă capacitatea mușuroiului i din primul oraș al țării furnicilor.
Pe următoarele N-1 linii se găsesc câte șase întregi P, X, Y, V, Z, T care descriu parametrii folosiți în momentul în care creăm un nou oraș. P reprezintă indicele orașului din care se va forma un oraș nou. Indicele orașului inițial este 1. Fiecărui nou oraș întemeiat îi vom asocia un indice egal cu cel mai mic întreg pozitiv care nu a fost folosit ca indice pentru un oraș deja construit. Numerele L, R, i, j din enunț sunt generate astfel:
L = ((X+S) mod M) + 1
R = ((Y+S) mod M) + 1
i = ((Z+S) mod M) + 1
j = ((T+S) mod M) + 1
Unde S este inițial 0, iar după construirea unui oraș nou, valoarea lui S va fi actualizată astfel încât să fie egală cu numărul de furnici care pot locui în cartierul select al celui mai recent oraș nou construit, constând din toate mușuroaiele cu indici între i și j inclusiv. Această valoare va fi folosită la calcularea parametrilor pentru construcția următorului oraș (următorul din lista din input). Se garantează că L ≤ R și i ≤ j pentru fiecare oraș.

Date de ieșire

Pentru fiecare oraș nou construit, afișați în fișierul ants.out câte un întreg pe o linie: S – numărul de furnici care pot locui în cartierul select al acelui oraș.

Restricții

1 ≤ N ≤ 50000
1 ≤ M ≤ 100000
0 ≤ A_i, V ≤ 100000 pentru orice i între 1 și M, și orice V al fiecărui oraș nou construit
1 ≤ L ≤ R ≤ M pentru fiecare oraș nou construit
1 ≤ i ≤ j ≤ M pentru fiecare oraș nou construit
0 ≤ X, Y, Z, T < M
Pentru l0% din punctaj, N, M ≤ 1000.
Pentru 30% din punctaj, pentru fiecare oraș nou construit, P va fi egal cu indicele orașului care a fost întemeiat exact înaintea orașului curent.

Exemplu

Explicație

După toate operațiile, vom avea 4 orașe. În fiecare oraș vom avea 4 mușuroaie.
Mușuroaiele din orașul 1 au capacitățile {3, 6, 7, 5}. Când creăm orașul cu numărul 2, S = 0, L = 3, R = 4, i = 1, j = 2, V = 1. Capacitățile musuroaielor din orașul 2 vor fi deci {3, 6, 8, 6} și numărul de furnici care pot locui în cartierul select este 3 + 6 = 9. Setăm S = 9 înainte să construim noul oraș.
La momentul creării orașului 3, S = 9. Se calculează L = ((1 + 9) mod 4) + 1 = 3, R = 4, i = ((2 + 9) mod 4) + 1 = 4, j = 4, V = 6. Cum orașul 3 s-a format în urma suprapopulării orașului 2, furnicile vor încerca să păstreze capacitățile din orașul 2 cu schimbări minore. Capacitățile din orașul 3 sunt {3, 6, 14, l2}. Cartierul select este format doar din mușuroiul 4 care are capacitatea 12. Setăm S = 12 înaintea trecerii la orașul 4.
Orașul 4 se construiește în urma suprapopulării orașului 1. Cu noua valoare a lui S calculăm L = 1, R = 3, i = 1, j = 4, V = 8. Capacitățile sunt {11, 14, 15, 5}. Toate mușuroaiele sunt în cartierul select: 11 + 14 + 15 + 5 = 45.