농부 존은 $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$개 미만의 건초가 있다면, 소는 아무것도 하지 않습니다.

각 더미에 대해, 존은 더미가 빌 때까지 소를 순차적으로(같은 소를 여러 번 고용할 수도 있음) 고용하여 모든 건초를 제거하고자 합니다. 각 더미를 비우는 데 드는 최소 비용을 구하도록 존을 도와주세요.

입력

첫 번째 줄에는 독립적인 테스트 케이스의 수 $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: 추가 제약 없음.