Farmer John a $N$ piles de bottes de foin ($1 \leq N \leq 5 \cdot 10^5$), où la $i$-ième pile contient $a_i$ bottes de foin ($1 \leq a_i \leq 10^9$). Il veut retirer toutes ces bottes de foin et dispose de $M$ ($1 \leq M \leq 2500$) vaches pour l'aider. Si elle est embauchée, la $i$-ième vache répétera ce qui suit $s_i$ fois ($1 \leq s_i \leq 100$) pour un coût de $c_i$ ($1 \leq c_i \leq 10^9$) :

• Si la pile contient au moins $p_i$ bottes de foin ($1 \leq p_i \leq 10^9$), alors la vache retirera une botte de foin.
• Si la pile contient moins de $p_i$ bottes de foin, la vache ne fait rien.

Pour chaque pile, FJ veut retirer toutes les bottes de foin qu'elle contient. Il procédera en embauchant des vaches en séquence (éventuellement la même vache plus d'une fois) jusqu'à ce que la pile devienne vide. Aidez FJ à déterminer, pour chaque pile, le coût minimal pour la vider.

Entrée

L’entrée provient du terminal / stdin.

La première ligne contient $T$ ($1\le T\le 100$), le nombre de tests indépendants. Chaque test est formaté comme suit :

La première ligne contient un entier $N$. La deuxième ligne contient $N$ entiers, $a_1, a_2, \dots, a_N$.

La troisième ligne contient un entier $M$. Ensuite, les $M$ lignes suivantes contiendront $p_i, s_i, c_i$.

Il est garanti que les vaches pourront retirer toutes les bottes de foin de chaque pile. De plus, il est garanti que la somme des $N$ sur tous les tests ne dépasse pas $5\cdot 10^5$, et que la somme des $M$ sur tous les tests ne dépasse pas $2500$.

Sortie

Affichez la sortie sur le terminal / stdout.

Pour chaque test, affichez $N$ entiers séparés par des espaces, le $i$-ième entier étant le coût pour retirer toutes les bottes de foin de la $i$-ième pile.

Exemples

Entrée 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

Sortie 1

29 155 21
73 328 50

Remarque

Premier test : Pour la dernière pile de taille initiale $10$, nous pouvons embaucher la vache $3$ une fois, ce qui coûte $5$ et retirera deux bottes de foin (pas trois car le nombre de bottes de foin devient $8$ après que la deuxième est retirée). Ensuite, nous pouvons embaucher la vache $2$ deux fois, retirant les $8$ bottes de foin, ce qui fait qu'il ne reste plus de bottes de foin. Le coût total est $ 5+8+8=21$.

Deuxième test : Cela satisfait $\max(s)=1$.

Sous-tâches

• Entrées 2-3 : $a_i \le 100$
• Entrées 4-5 : $\max(s)=1$
• Entrées 6-9 : $\max(s)\le 4$
• Entrées 10-15 : $\max(s)\le 20$
• Entrées 16-21 : Aucune contrainte supplémentaire.

Crédits du problème : Sujay Konda