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$ 头奶牛将花费 $c_i$（$1 \leq c_i \leq 10^9$）重复以下操作 $s_i$ 次（$1 \leq s_i \leq 100$）：

• 如果堆中至少包含 $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