题目背景

译自 COCI 2023/2024 Contest #3 T2「Vrsar」

题目描述

Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。

Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsar 停留的每一天都以溜冰度过。在第 $i$ 天的开始，他们距离海岸 $a_i$ 米。当滑雪场开放的同时，他们开始他们的溜冰之旅。他们需要走去滑雪场，走路的速度为每分钟 $1$ 米。

他们的身体非常好，因此他们不需要额外时间来爬山。一旦他们到达山顶的滑雪场，他们可以滑任意长的时间，直到滑雪场关闭。然而，下山并不像上山一样容易，因为下雨，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i$ 座山。从一座山上下来后，他们可以前往另一座山。

Iva 和 Mia 想知道每天他们最长可以滑多久的雪。每天他们可以访问任意多座滑雪场。因为他们想用尽可能多的时间滑雪，用尽可能少的时间计算，所以他们向你寻求帮助。帮助他们解决这个问题。

请注意：如果 Iva 和 Mia 早晨出发的位置就有一座山，他们在山脚。

输入格式

第一行包含两个整数 $n,m$（$1 \le n,m \le 10^5$），表示山的数量和天数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,t_i,s_i$（$0 \le x_i,t_i,s_i \le 10^9$），分别表示第 $i$ 座山到海岸的距离、滑雪场的关闭时间和下山所需的时间。

第三行包含 $m$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示 Iva 和 Mia 第 $i$ 天出发时到海岸的距离。

输出格式

输出一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 天 Iva 和 Mia 可以滑雪的最长时间。

3 1
3 7 0
6 11 3
10 13 5
1

6

3 2
5 10 3
3 6 1
1 5 0
0 3

5 8

1 3
3 3 3
0 1 2

0 1 2

提示

样例解释 1

Iva 和 Mia 在位置 $1$ 出发，走 $2$ 分钟到位置 $3$ 的山，并滑雪 $5$ 分钟。接着花费 $0$ 分钟时间下山，继续走 $3$ 分钟时间到位置 $6$ 山上的滑雪场，滑雪 $1$ 分钟。

他们一共滑雪 $6$ 分钟。

子任务