Farmer John ma $N$ stosów bel 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 usunąć wszystkie te bele siana i ma $M$ ($1 \leq M \leq 2500$) dostępnych krów, które mogą mu pomóc. Jeśli zostanie wynajęta, $i$-ta krowa powtórzy następującą 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$), to krowa usunie jedną belę siana.
• Jeśli stos zawiera mniej niż $p_i$ bel siana, krowa nic nie robi.

Dla każdego stosu FJ chce usunąć wszystkie bele siana w nim. Zrobi to, wynajmując krowy po kolei (być może tę samą krowę więcej niż raz), aż stos stanie się pusty. Pomóż FJ ustalić dla każdego stosu minimalny koszt jego opróżnienia.

Wejście

Dane wejściowe pochodzą z terminala / stdin.

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

Pierwszy wiersz zawiera liczbę całkowitą $N$. Drugi wiersz zawiera $N$ liczb całkowitych, $a_1, a_2, \dots, a_N$.

Trzeci wiersz zawiera liczbę całkowitą $M$. Następne $M$ wierszy będą 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$ po wszystkich testach nie przekracza $5\cdot 10^5$, a suma $M$ po wszystkich testach nie przekracza $2500$.

Wyjście

Wypisz wynik do terminala / stdout.

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 raz wynająć krowę numer $3$, co kosztuje $5$ i usunie bele siana dwukrotnie (nie trzy razy, ponieważ liczba bel siana spada do $8$ po usunięciu drugiej). Następnie możemy dwa razy wynająć krowę numer $2$, usuwając $8$ bel siana, w wyniku czego nie pozostanie żadna bela siana. Całkowity koszt wynosi $ 5+8+8=21$.

Drugi test spełnia $\max(s)=1$.

Podzadania

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

Autor zadania: Sujay Konda