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 計算每一堆乾草清空所需的最低成本。

第一行包含 $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$。

對於每個測試資料，輸出 $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：無額外限制。