Farmer John ma $N$ stosów siana ($1 \leq N \leq 5 \cdot 10^5$), gdzie $i$-ty stos zawiera $a_i$ bel siana ($1 \leq a_i \leq 10^9$). Chce on usunąć wszystkie te bele i ma do pomocy $M$ ($1 \leq M \leq 2500$) krów. Jeśli zostanie zatrudniona, $i$-ta krowa powtórzy poniższą czynność $s_i$ razy ($1 \leq s_i \leq 100$) za koszt $c_i$ ($1 \leq c_i \leq 10^9$):

• Jeśli stos zawiera co najmniej $p_i$ bel siana ($1 \leq p_i \leq 10^9$), krowa usunie jedną belę.
• Jeśli stos zawiera mniej niż $p_i$ bel siana, krowa nie robi nic.

Dla każdego stosu FJ chce usunąć wszystkie znajdujące się w nim bele. Będzie to robił, zatrudniając krowy w kolejności (możliwe jest zatrudnienie tej samej krowy więcej niż raz), aż stos stanie się pusty. Pomóż FJ wyznaczyć dla każdego stosu minimalny koszt jego opróżnienia.

Wejście

Pierwsza linia zawiera $T$ ($1 \le T \le 100$), liczbę niezależnych testów. Każdy test ma następujący format:

Pierwsza linia zawiera liczbę całkowitą $N$. Druga linia zawiera $N$ liczb całkowitych $a_1, a_2, \dots, a_N$.

Trzecia linia zawiera liczbę całkowitą $M$. Następnie $M$ linii zawiera $p_i, s_i, c_i$.

Gwarantuje się, że krowy będą w stanie usunąć wszystkie bele siana z każdego stosu. Dodatkowo gwarantuje się, że suma $N$ we wszystkich testach nie przekracza $5\cdot 10^5$, a suma $M$ we wszystkich testach nie przekracza $2500$.

Wyjście

Dla każdego testu wypisz $N$ liczb całkowitych oddzielonych spacjami, gdzie $i$-ta liczba to koszt usunięcia wszystkich bel siana z $i$-tego stosu.

Przykład

Wejście 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

Wyjście 1

29 155 21
73 328 50

Uwagi

Pierwszy test: Dla ostatniego stosu o początkowym rozmiarze $10$, możemy zatrudnić krowę $3$ raz, co kosztuje $5$ i usunie bele dwukrotnie (nie trzykrotnie, ponieważ liczba bel zmienia się na $8$ po usunięciu drugiej). Następnie możemy zatrudnić krowę $2$ dwa razy, usuwając $8$ bel, co skutkuje brakiem pozostałych bel. Całkowity koszt wynosi $5+8+8=21$.

Drugi test: Spełnia warunek $\max(s)=1$.

Podzadania

• Testy 2-3: $a_i \le 100$
• Testy 4-5: $\max(s)=1$
• Testy 6-9: $\max(s)\le 4$
• Testy 10-15: $\max(s)\le 20$
• Testy 16-21: Brak dodatkowych ograniczeń.