Haybale Stacks
**Note: The time limit for this problem is 2.5s.**
Farmer John has N stacks of haybales (1≤N≤5⋅105), where the ith stack contains ai haybales (1≤ai≤109). He wants to remove all of these haybales and has M (1≤M≤2500) cows available to help him. If hired, the ith cow will repeat the following si times (1≤si≤100) for a cost of ci (1≤ci≤109):
- If the stack contains at least pi haybales (1≤pi≤109), then the cow will remove one haybale.
- If the stack contains less than pi 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.
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.
SCORING:
- Inputs 2-3: ai≤100
- Inputs 4-5: max(s)=1
- Inputs 6-9: max(s)≤4
- Inputs 10-15: max(s)≤20
- Inputs 16-21: No additional constraints.
Problem credits: Sujay Konda
Source: USA Computing Olympiad.
Input Format
The first line contains T (1≤T≤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, a1,a2,…,aN.
The third line contains an integer M. Then the next M lines will contain pi,si,ci.
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⋅105, and the sum of M over all tests does not exceed 2500.
Output Format
For each test, print N space-separated integers, the ith integer being the cost of removing all the haybales in the ith stack.