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：无额外限制。

题目来源：Sujay Konda