Fişierul intrare/ieşire:	galerie.in, galerie.out	Sursă	.com 2009, Runda 1
Autor	Serban Andrei Stan	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.35 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Galerie

Cârtiţele din toată ţara se vor aduna în săptămânile următoare în oraşul Văgăuna, cu ocazia "Meeting-ului Anual al Cârtiţelor". Participanţii au fost cazaţi la hotel Subpământ în N camere, fiecare cameră având V_i cârtiţe. Camerele sunt aşezate pe un coridor în ordine de la 1 la N. Cum cârtiţele sunt animale înclinate spre socializare, organizatorii iau în calcul derularea a M vizite. Mai exact, se stie ca dintr-o camera P vor pleca C cartiţe spre altă camera Q. Pentru ca cele C cârtiţe sa ajunga în camera Q ele trebuie sa treacă prin toate camerele ce despart P de Q. Timpul petrecut pe drum se va calcula astfel: |P-Q|*C. Organizatorii sunt conştienţi de faptul ca membrii meeting-ului pot pierde foarte multă vreme cu vizitele, şi astfel îşi pun T întrebări de tipul: dacă am construi o galerie de la camera X la camera Y, care ar fi parcursă de fiecare cârtiţă într-un timp K, cu cât s-ar îmbunătăţii suma timpilor necesari pentru derularea celor M vizite?

Cerinţă

Ajutaţi-i pe organizatori să răspundă la cele T întrebări.

Date de intrare

Pe prima linie a fişierului de intrare galerie.in se vor afla trei numere naturale N,M si T cu semnificaţia din enunţ. Pe a doua linie se vor găsi numerele V₁,V₂...V_n, reprezentând numărul de cârtite cazate în fiecare cameră de la 1 la N. Următoarele M linii vor conţine câte trei numere naturale P,Q,C descriind faptul ca C cârtiţe pleacă din camera P spre camera Q. Pe fiecare din următoarele T linii se vor găsi cate trei numere X,Y,K descriind câte o întrebare a organizatorilor.

Date de ieşire

Fişierul de ieşire galerie.out va conţine T linii, pe fiecare linie câte un număr D_i, reprezentând raspunsul la a i-a întrebare pusă de organizatori.

Restricţii

• 1 ≤ T ≤ 250 000
• 1 ≤ N, M ≤ 100 000
• 1 ≤ P, Q, X, Y, K ≤ N
• P ≠ Q, X ≠ Y
• 0 ≤ C, V_i ≤ 50
• Pentru 40% din teste se garantează T,M ≤ 1000
• Dintr-o camera nu vor pleca în vizite mai multe cârtiţe decât au fost cazate
• Cârtiţele vor parcurge camerele în sens strict crescător sau strict descrescător
• Dintr-o cameră P din care nu porneşte o galerie, cârtiţele se pot deplasa doar în camera P-1 sau P+1

Exemplu

Explicaţie

Dacă nu este construită vreo galerie cârtiţele urmează traseul 1-2,2-3,3-4, şi ajung în timp total 2*3=6. În cazul primei întrebări, traseul ales va fi 1-3,3-4, fiind parcurs în timp 4. Timpul final se îmbunataţeşte cu 2.

Cum se trimit solutii?