Farmer John có $N$ đống cỏ khô ($1 \leq N \leq 5 \cdot 10^5$), trong đó đống thứ $i$ chứa $a_i$ bó cỏ khô ($1 \leq a_i \leq 10^9$). Ông ấy muốn dọn hết số cỏ khô này và có $M$ ($1 \leq M \leq 2500$) con bò sẵn sàng giúp. Nếu được thuê, con bò thứ $i$ sẽ lặp lại thao tác sau $s_i$ lần ($1 \leq s_i \leq 100$) với chi phí $c_i$ ($1 \leq c_i \leq 10^9$):

• Nếu đống cỏ chứa ít nhất $p_i$ bó cỏ khô ($1 \leq p_i \leq 10^9$), thì con bò sẽ dọn đi một bó cỏ khô.
• Nếu đống cỏ chứa ít hơn $p_i$ bó cỏ khô, con bò không làm gì.

Với mỗi đống, FJ muốn dọn hết số cỏ khô trong đó. Ông ấy sẽ làm điều này bằng cách thuê các con bò theo thứ tự (có thể thuê cùng một con bò nhiều hơn một lần) cho đến khi đống cỏ trở nên trống. Hãy giúp FJ xác định với mỗi đống chi phí tối thiểu để dọn trống nó.

Dữ liệu vào

Dữ liệu vào đến từ thiết bị đầu cuối / stdin.

Dòng đầu tiên chứa $T$ ($1\le T\le 100$), số lượng bộ kiểm thử độc lập. Mỗi bộ kiểm thử được định dạng như sau:

Dòng đầu tiên chứa một số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên, $a_1, a_2, \dots, a_N$.

Dòng thứ ba chứa một số nguyên $M$. Sau đó, $M$ dòng tiếp theo sẽ chứa $p_i, s_i, c_i$.

Đảm bảo rằng những con bò sẽ có thể dọn hết cỏ khô trong mọi đống. Ngoài ra, đảm bảo rằng tổng của $N$ qua tất cả các bộ kiểm thử không vượt quá $5\cdot 10^5$, và tổng của $M$ qua tất cả các bộ kiểm thử không vượt quá $2500$.

Dữ liệu ra

In dữ liệu ra ra thiết bị đầu cuối / stdout.

Với mỗi bộ kiểm thử, in ra $N$ số nguyên cách nhau bởi dấu cách, số nguyên thứ $i$ là chi phí để dọn hết cỏ khô trong đống thứ $i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

29 155 21
73 328 50

Ghi chú

Bộ kiểm thử thứ nhất: Với đống cuối cùng có kích thước ban đầu $10$, ta có thể thuê bò $3$ một lần, tốn $5$ và sẽ dọn được hai bó cỏ khô (không phải ba vì số bó cỏ khô trở thành $8$ sau khi bó thứ hai bị dọn). Sau đó ta có thể thuê bò $2$ hai lần, dọn được $8$ bó cỏ khô, dẫn đến không còn bó cỏ khô nào. Tổng chi phí là $ 5+8+8=21$.

Bộ kiểm thử thứ hai: Bộ này thỏa mãn $\max(s)=1$.

Nhiệm vụ con

• Dữ liệu vào 2-3: $a_i \le 100$
• Dữ liệu vào 4-5: $\max(s)=1$
• Dữ liệu vào 6-9: $\max(s)\le 4$
• Dữ liệu vào 10-15: $\max(s)\le 20$
• Dữ liệu vào 16-21: Không có ràng buộc bổ sung.

Nguồn bài toán: Sujay Konda