== include(page="template/taskheader" task_id="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$.

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. 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ăţi suma timpilor necesari pentru derularea celor $M$ vizite?

h2. Cerinţă

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

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

h2. 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.

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ţ. 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.

h2. 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.

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.

h2. Restricţii

* $1 ≤ N, M, T ≤ 100 000$

* $1 ≤ T ≤ 250 000$
* $1 ≤ N, M ≤ 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

* $P ≠ Q, X ≠ Y$
* $0 ≤ C ≤ 50$
* Pentru $20%$ din teste se garantează $T,M ≤ 1 000$
* 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$
* Cârtiţele nu sunt obligate să folosească galeriile

h2. Exemplu
table(example). |_. galerie.in |_. galerie.out |
| 4 1 1

3 4 0 2

1 4 2
1 3 1
| 2

h3. Explicaţie

În mod normal cârtiţele ar urma traseul $1-2,2-3,3-4$, în timp $(4-1)*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$.

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$.

== include(page="template/taskfooter" task_id="galerie") ==

4269