問題文

パ研楽団には、 N 人の演奏者がいます。また、パ研楽団は M 種類の楽器を所有しています。i 人目の演奏者の熟練度は A_i で担当楽器は B_i 、楽器の移行コストは C_i です。i 人目の演奏者は C_i の移行コストで担当の楽器を好きなものに変更することができます。

楽団の調和度を以下のように定義します。

• M 種類の楽器それぞれについて、その楽器を担当する人の熟練度の最大値を考える。この M 個の値の最小値が調和度である。ただし、担当する人がいない楽器が存在する場合、調和度は 0 である。

x = X_1, X_2, \ldots ,X_Q について、移行コストの総和が x を超えずに実現できる最大の調和度を求めてください。

制約

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• 1 \leq B_i \leq M \ (1 \leq i \leq N)
• 0 \leq C_i \leq 10^9 \ (1 \leq i \leq N)
• 0 \leq X_1 < X_2 < \cdots < X_Q \leq 2 \times 10^{14}
• 入力は全て整数

小課題

1. (150 点) N, Q \leq 2000
2. (150 点) M \leq 10
3. (300 点) 追加の制約はない

入力例 1

5 3
7 1 4
10 3 3
8 3 3
9 3 5
7 1 4
6
2 9 12 15 25 46

出力例 1

0
8
8
8
8
8

例えば人 2 の担当楽器を 2 に、人 3 の担当楽器を 1 にすると調和度は 8 になります。このときかかるコストは C_2+C_3=6 です。

誰一人担当楽器を変えないと、調和度は 0 になります。このときかかるコストは 0 です。

入力例 2

10 6
10 3 4
12 2 5
2 1 3
7 3 15
12 1 10
8 3 3
11 3 14
13 6 9
3 3 12
4 5 1
10
1 3 7 37 53 85 88 91 94 148

出力例 2

0
4
8
8
8
8
8
8
8
8