**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.
INPUT FORMAT (input arrives from the terminal / stdin):
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 (print output to the terminal / stdout):
For each test, print N space-separated integers, the ith integer being the cost of removing all the haybales in the ith stack.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
29 155 21
73 328 50
First test: For the last stack of initial size 1010, we can hire cow 33 once, which costs 55 and will remove haybales twice (not thrice because the number of haybales turns to 88 after the second one is removed). Then we can hire cow 22 twice, removing the 88 haybales, resulting in no haybales left. The total cost is 5+8+8=215+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
