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 adună în următoarele săptămâni in oraşul Văgăuna, cu ocazia "Meeting-ului Anual al Cârtiţelor de Pretutindeni". Participanţii au fost cazaţi la hotel Subpământ în N camere, fiecare camera avand V_i cârtiţe. Camerele sunt aşezate în linie, în ordine de la 1 la N. Cum cârtiţele sunt animale înclinate spre socializare, organizatorii iau in calcul derularea a M vizite după ce toate cazarea tuturor cârtiţelor. 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 de cele C cârtiţe se va calcula astfel: abs(P-Q)*C. Organizatorii sunt conştienţi de faptul ca membrii meeting-ului pot pierde astfel foarte mult timp pe drum, şi astfel îşi pun T întrebări de tipul: daca am construi o galerie de la X la Y care ar fi parcursă într-un timp K, cu cât s-ar îmbunatăţii suma timpilor parcurşi de cartiţe? O galerie poate fi parcursa de C cârtiţe in timp C*K.

Cerinţă

Ajutaţi-i pe organizatori sa raspundă la cele T întrebări.

Date de intrare

Pe prima linie a fişierului de intrare galerie.in se vor afla teri numere naturale N, M si T cu semnificaţia din enunţ. Pe a doua linie se vor gasi V_i numere, mai exact numărul de cârtite cazate în camera i. a Urmatoarele 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. Urmatoarele T linii vor conţine 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 pusa de organizatori.

Restricţii

• 1 ≤ N, M, T ≤ 100 000
• 1 ≤ P, Q, X, Y, K ≤ N
• 0 ≤ C ≤ V_i
• Dintr-o camera nu vor pleca în vizită mai multe cârtiţe decât s-au cazat
• Cârtiţele vor parcurge camerele în sens strict crescător sau strict descrescător

Exemplu

Explicaţie

În mod normal cârtiţele ar urma traseul 1-2,2-3,3-4, în timp *2=6. Dupa construcţia galeriei drumul lor va fi 1-3,3-4. 1-3 va fi parcurs în timp 1*2, iar 3-4 tot în 1*2. Timpul total este 4 în acest caz, deci răspunsul va fi 6-4=2.

Cum se trimit solutii?