Farmer John possède $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 souhaite 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ète l'opération suivante $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 retire 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 y parviendra en embauchant des vaches successivement (éventuellement la même vache plusieurs fois) jusqu'à ce que la pile soit vide. Aidez FJ à déterminer, pour chaque pile, le coût minimal pour la vider.

Entrée

La première ligne contient $T$ ($1 \leq T \leq 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 contiennent $p_i, s_i, c_i$.

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

Sortie

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 des bottes de foin deux fois (pas trois fois car le nombre de bottes de foin devient $8$ après que la deuxième a été retirée). Ensuite, nous pouvons embaucher la vache $2$ deux fois, retirant les $8$ bottes de foin, ce qui ne laisse aucune botte de foin. Le coût total est $5+8+8=21$.

Second test : Ceci 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.