Farmer John có $N$ đống kiện cỏ ($1 \leq N \leq 5 \cdot 10^5$), trong đó đống thứ $i$ chứa $a_i$ kiện cỏ ($1 \leq a_i \leq 10^9$). Ông ấy muốn dọn sạch tất cả các kiện cỏ 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 quy trình 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$ kiện ($1 \leq p_i \leq 10^9$), con bò sẽ lấy đi một kiện cỏ.
• Nếu đống cỏ chứa ít hơn $p_i$ kiện, con bò không làm gì cả.

Với mỗi đống cỏ, FJ muốn dọn sạch hoàn toàn. Ông ấy sẽ thực hiện việc này bằng cách thuê các con bò theo trình tự (có thể thuê cùng một con bò nhiều lần) cho đến khi đống cỏ trở nên trống rỗng. Hãy giúp FJ xác định chi phí tối thiểu để dọn sạch từng đống cỏ.

Dữ liệu vào

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

Dòng đầu tiên chứa 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 số nguyên $M$. Sau đó, $M$ dòng tiếp theo chứa $p_i, s_i, c_i$.

Đảm bảo rằng các con bò luôn có khả năng dọn sạch tất cả các kiện cỏ trong mọi đống. Ngoài ra, tổng $N$ trên tất cả các bộ dữ liệu không vượt quá $5\cdot 10^5$ và tổng $M$ trên tất cả các bộ dữ liệu không vượt quá $2500$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra $N$ số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ $i$ là chi phí tối thiểu để dọn sạch đống cỏ 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ộ dữ liệu thứ nhất: Đối với đống cỏ cuối cùng có kích thước ban đầu là $10$, chúng ta có thể thuê con bò thứ $3$ một lần, chi phí là $5$ và nó sẽ lấy đi kiện cỏ hai lần (không phải ba lần vì số lượng kiện cỏ giảm xuống $8$ sau khi kiện thứ hai được lấy đi). Sau đó, chúng ta có thể thuê con bò thứ $2$ hai lần, lấy đi $8$ kiện cỏ còn lại, kết quả là đống cỏ trống rỗng. Tổng chi phí là $5+8+8=21$.

Bộ dữ liệu thứ hai: Thỏa mãn điều kiện $\max(s)=1$.

Nhiệm vụ con

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