Farmer John 有 $N$ 堆乾草捆（$1 \leq N \leq 5 \cdot 10^5$），其中第 $i$ 堆含有 $a_i$ 個乾草捆（$1 \leq a_i \leq 10^9$）。他想移除所有這些乾草捆，並有 $M$（$1 \leq M \leq 2500$）頭牛可幫助他。若雇用第 $i$ 頭牛，牠會重複以下動作 $s_i$ 次（$1 \leq s_i \leq 100$），花費為 $c_i$（$1 \leq c_i \leq 10^9$）：
- 若該堆含有至少 $p_i$ 個乾草捆（$1 \leq p_i \leq 10^9$），則該牛會移除一個乾草捆。
- 若該堆含有少於 $p_i$ 個乾草捆，則該牛不做任何事。
對於每一堆，FJ 想要移除其中的所有乾草捆。他會依序雇用牛（可能多次雇用同一頭牛），直到該堆變空。請幫助 FJ 求出清空每一堆所需的最小花費。
輸入格式
輸入來自終端 / stdin。
第一行包含 $T$（$1\le T\le 100$），表示獨立測試的數量。 每個測試的格式如下：
第一行包含一個整數 $N$。第二行包含 $N$ 個整數，$a_1, a_2, \dots, a_N$。
第三行包含一個整數 $M$。接下來 $M$ 行會包含 $p_i, s_i, c_i$。
保證牛能夠移除每一堆中的所有乾草捆。此外，保證所有測試的 $N$ 總和不超過 $5\cdot 10^5$，且所有測試的 $M$ 總和不超過 $2500$。
輸出格式
將輸出列印至終端 / stdout。
對於每個測試，輸出 $N$ 個以空格分隔的整數，第 $i$ 個整數為移除第 $i$ 堆中所有乾草捆的花費。
範例
輸入格式 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輸出格式 1
29 155 21
73 328 50說明
第一個測試：對於初始大小為 $10$ 的最後一堆，我們可以雇用第 $3$ 頭牛一次，花費 $5$，且會移除乾草捆兩次（不是三次，因為移除第二個之後乾草捆數量變成 $8$）。接著我們可以雇用第 $2$ 頭牛兩次，移除 $8$ 個乾草捆，最後沒有剩下任何乾草捆。總花費為 $ 5+8+8=21$。
第二個測試：這滿足 $\max(s)=1$。
子任務
- 輸入 2-3：$a_i \le 100$
- 輸入 4-5：$\max(s)=1$
- 輸入 6-9：$\max(s)\le 4$
- 輸入 10-15：$\max(s)\le 20$
- 輸入 16-21：無額外限制。
題目鳴謝：Sujay Konda