Farmer John hat $N$ Heuballenstapel ($1 \leq N \leq 5 \cdot 10^5$), wobei der $i$-te Stapel $a_i$ Heuballen enthält ($1 \leq a_i \leq 10^9$). Er möchte alle Heuballen entfernen und hat $M$ ($1 \leq M \leq 2500$) Kühe, die ihm helfen können. Wird die $i$-te Kuh angeheuert, wiederholt sie die folgende Handlung $s_i$-mal ($1 \leq s_i \leq 100$) für einen Preis von $c_i$ ($1 \leq c_i \leq 10^9$):

• Enthält der Stapel mindestens $p_i$ Heuballen ($1 \leq p_i \leq 10^9$), entfernt die Kuh einen Heuballen.
• Enthält der Stapel weniger als $p_i$ Heuballen, tut die Kuh nichts.

FJ möchte jeden Stapel vollständig leeren. Dazu heuert er nacheinander Kühe an (möglicherweise dieselbe Kuh mehrmals), bis der Stapel leer ist. Hilf FJ, für jeden Stapel die minimalen Kosten zum Leeren zu bestimmen.

Eingabe

Die Eingabe erfolgt über das Terminal / stdin.

Die erste Zeile enthält $T$ ($1\le T\le 100$), die Anzahl unabhängiger Tests. Jeder Test hat folgendes Format:

Die erste Zeile enthält eine ganze Zahl $N$. Die zweite enthält $N$ ganze Zahlen, $a_1, a_2, \dots, a_N$.

Die dritte Zeile enthält eine ganze Zahl $M$. Die nächsten $M$ Zeilen enthalten jeweils $p_i, s_i, c_i$.

Es ist garantiert, dass die Kühe alle Heuballen aus jedem Stapel entfernen können. Außerdem beträgt die Summe von $N$ über alle Tests höchstens $5\cdot 10^5$ und die Summe von $M$ höchstens $2500$.

Ausgabe

Gib das Ergebnis im Terminal / stdout aus.

Gib für jeden Test $N$ durch Leerzeichen getrennte ganze Zahlen aus. Die $i$-te Zahl sind die Kosten zum Entfernen aller Heuballen aus dem $i$-ten Stapel.

Beispiele

Eingabe 1

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

Ausgabe 1

29 155 21
73 328 50

Hinweis

Erster Test: Für den letzten Stapel mit anfänglich $10$ Heuballen können wir Kuh $3$ einmal anheuern. Das kostet $5$ und entfernt zweimal einen Heuballen (nicht dreimal, weil nach dem zweiten entfernten Ballen nur noch $8$ Ballen übrig sind). Danach können wir Kuh $2$ zweimal anheuern und die $8$ Heuballen entfernen, sodass keiner übrig bleibt. Die Gesamtkosten sind $ 5+8+8=21$.

Zweiter Test: Hier gilt $\max(s)=1$.

Teilaufgaben

• Eingaben 2-3: $a_i \le 100$
• Eingaben 4-5: $\max(s)=1$
• Eingaben 6-9: $\max(s)\le 4$
• Eingaben 10-15: $\max(s)\le 20$
• Eingaben 16-21: Keine zusätzlichen Einschränkungen.

Autor der Aufgabe: Sujay Konda