Haybale Stacks

Note: The time limit for this problem is 2.5s.

Farmer John has $N$ stacks of haybales ($1 \leq N \leq 5 \cdot 10^5$), where the $i$th stack contains $a_i$ haybales ($1 \leq a_i \leq 10^9$). He wants to remove all of these haybales and has $M$ ($1 \leq M \leq 2500$) cows available to help him. If hired, the $i$th cow will repeat the following $s_i$ times ($1 \leq s_i \leq 100$) for a cost of $c_i$ ($1 \leq c_i \leq 10^9$):

• If the stack contains at least $p_i$ haybales ($1 \leq p_i \leq 10^9$), then the cow will remove one haybale.
• If the stack contains less than $p_i$ haybales, the cow does nothing.

For each stack, FJ wants to remove all of the haybales in it. He will do this by hiring cows in sequence (possibly the same cow more than once) until the stack becomes empty. Help FJ determine for each stack the minimum cost to empty it.

The first line contains $T$ ($1\le T\le 100$), the number of independent tests. Each test is formatted as follows:

The first line contains an integer $N$. The second line contains $N$ integers, $a_1, a_2, \dots, a_N$.

The third line contains an integer $M$. Then the next $M$ lines will contain $p_i, s_i, c_i$.

It is guaranteed that the cows will be able to remove all the haybales in every stack. Additionally, it is guaranteed that the sum of $N$ over all tests does not exceed $5\cdot 10^5$, and the sum of $M$ over all tests does not exceed $2500$.

• Inputs 2-3: $a_i \le 100$
• Inputs 4-5: $\max(s)=1$
• Inputs 6-9: $\max(s)\le 4$
• Inputs 10-15: $\max(s)\le 20$
• Inputs 16-21: No additional constraints.

For each test, print $N$ space-separated integers, the $i$th integer being the cost of removing all the haybales in the $i$th stack.

First test: For the last stack of initial size $10$, we can hire cow $3$ once, which costs $5$ and will remove haybales twice (not thrice because the number of haybales turns to $8$ after the second one is removed). Then we can hire cow $2$ twice, removing the $8$ haybales, resulting in no haybales left. The total cost is $ 5+8+8=21$.

Second test: This satisfies $\max(s)=1$.