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$) を雇うことができます。ある牛を雇った場合、その牛は以下の手順を $s_i$ 回 ($1 \leq s_i \leq 100$) 繰り返します。このときのコストは $c_i$ ($1 \leq c_i \leq 10^9$) です。

• 山に $p_i$ 個以上の干し草がある場合 ($1 \leq p_i \leq 10^9$)、牛は干し草を 1 個取り除きます。
• 山の干し草が $p_i$ 個未満の場合、牛は何もしません。

FJ は各山について、その山が空になるまで牛を順番に雇う（同じ牛を複数回雇うことも可能）ことで、すべての干し草を取り除こうとしています。各山を空にするための最小コストを求めてください。

入力

最初の行には独立したテストケースの数 $T$ ($1 \le T \le 100$) が含まれます。各テストケースの形式は以下の通りです。

最初の行には整数 $N$ が含まれます。2 行目には $N$ 個の整数 $a_1, a_2, \dots, a_N$ が含まれます。

3 行目には整数 $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 番目の牛を 1 回雇うとコストは $5$ で、干し草を 2 回取り除きます（3 回ではないのは、2 回取り除いた時点で干し草が $8$ 個になるためです）。次に 2 番目の牛を 2 回雇うと残りの $8$ 個の干し草が取り除かれ、山は空になります。合計コストは $5+8+8=21$ です。

2 番目のテストケース：これは $\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: 追加の制約なし。