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$번째 소는 비용 $c_i$를 받고 다음 동작을 $s_i$번 반복한다($1 \leq s_i \leq 100$, $1 \leq c_i \leq 10^9$):

• 더미에 건초 베일이 $p_i$개 이상 있으면($1 \leq p_i \leq 10^9$), 소는 건초 베일 하나를 제거한다.
• 더미에 건초 베일이 $p_i$개 미만이면, 소는 아무것도 하지 않는다.

각 더미에 대해, FJ는 그 안의 모든 건초 베일을 제거하려고 한다. 그는 더미가 빌 때까지 소를 순서대로 고용하여(같은 소를 여러 번 고용할 수 있다) 이 작업을 수행한다. 각 더미를 비우는 최소 비용을 FJ가 구하도록 도와라.

입력

입력은 터미널 / stdin에서 주어진다.

첫 번째 줄에는 독립적인 테스트의 수 $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$을 넘지 않음이 보장된다.

출력

출력은 터미널 / stdout으로 출력한다.

각 테스트마다 공백으로 구분된 $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