海狸哈利经营着一家旅馆，在旅游旺季结束前的接下来的 $Q$ 周里，他每周日晚上都要清洗床单。在第 $j$ 周，他有 $N$ 条刚洗好的床单，需要把它们挂在两条长度均为 $L_j$ 的平行晾衣绳上晾干。床单可以并排悬挂，但不能重叠。每条床单的宽度为 $d_i$ 个单位，长度较长，因此他总是将床单按宽度方向悬挂，即每条床单在晾衣绳上占用 $d_i$ 个单位的长度。由于材质不同，床单的晾干时间也各不相同。第 $i$ 条床单如果只挂在一条晾衣绳上，需要 $t_i^{\text{slow}}$ 分钟晾干。然而，如果将其同时挂在两条晾衣绳上，它会干得更快，只需 $t_i^{\text{fast}}$ 分钟，但同时也会占用另一条晾衣绳上的空间。为了避免床单产生异味，海狸哈利必须在洗完后立即开始晾晒，即所有床单必须同时开始晾挂。

海狸哈利希望在周日晚上能尽早休息，因此他请求你帮助他确定每周 $j$ 所需的最短晾干时间，或者告知他该周无法完成所有床单的晾晒。

输入格式

第一行包含一个整数 $N$（床单数量）和一个整数 $Q$（旅游旺季结束前的周数）。接下来的 $N$ 行包含空格分隔的整数 $d_i$、$t_i^{\text{fast}}$ 和 $t_i^{\text{slow}}$，分别对应第 $i$ 条床单的宽度、较短晾干时间和较长晾干时间。最后 $Q$ 行包含整数 $L_j$，其中第 $j$ 个整数表示第 $j$ 周晾衣绳的长度。

数据范围

• $1 \le N \le 3 \cdot 10^4$
• $1 \le Q \le 3 \cdot 10^5$
• 对于所有 $1 \le i \le N$，$1 \le d_i \le 3 \cdot 10^5$
• 对于所有 $1 \le i \le N$，$1 \le t_i^{\text{fast}} \le t_i^{\text{slow}} \le 10^9$
• 对于所有 $1 \le j \le Q$，$1 \le L_j \le 3 \cdot 10^5$

输出格式

输出 $Q$ 行，第 $j$ 行包含第 $j$ 周所需的最短晾干时间，如果该周无法完成晾晒，则输出“-1”（不含引号）。

样例

输入 1

3 3
1 2 2
1 1 4
2 3 100
3
1
4

输出 1

4
-1
3