Vrsar 是一个小海滨城镇，由 $n$ 座小山组成。令人惊讶的是，从海上望去，所有小山都一座接一座地排列，使得第 $i$ 座小山距离海岸 $x_i$ 米。每座山顶都有一个溜冰场。所有溜冰场每天同时开放，但关闭时间不同：第 $i$ 个溜冰场开放时长为 $t_i$ 分钟。

Iva 和 Mia 来到 Vrsar，将在这里停留 $m$ 天。Iva 和 Mia 热爱滑冰，并希望在镇上的每一天都去滑冰。在第 $i$ 天开始时，她们距离海岸 $a_i$ 米，她们的滑冰冒险与溜冰场开放同时开始。为了到达溜冰场，她们必须步行前往，步行速度为每分钟一米。她们可以向左或向右走。如果她们所在的位置有山，她们可以选择爬上山到达山顶的溜冰场，也可以选择绕过它而不爬山。

她们身体素质很好，所以爬山不需要额外的时间。一旦到达山顶，她们可以随心所欲地滑冰，直到溜冰场关闭。下山不像上山那么容易。最近下过雨，地面很滑，所以下第 $i$ 座山需要 $s_i$ 分钟。从山上下来后，她们可以继续向下一个溜冰场走去。

该插图展示了第一个样例。

Iva 和 Mia 在位置 1 的起点。她们步行 2 分钟到达位置 3 的山顶溜冰场，并在那里滑冰 5 分钟。然后她们下山（耗时 0 分钟），继续步行 3 分钟到达位置 6 的山顶溜冰场，并在那里滑冰 1 分钟。总共，她们滑冰了 $5 + 1 = 6$ 分钟。

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$ ($0 \le a_i \le 10^9$)，表示 Iva 和 Mia 在第 $i$ 天开始时距离海岸的距离。

输出格式

输出一行，包含 $m$ 个整数，其中第 $i$ 个整数表示 Iva 和 Mia 在第 $i$ 天能滑冰的最大时长。

子任务

样例

输入 1

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

输出 1

6

说明 1

请查看题目描述中的插图。

输入 2

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

输出 2

5 8

输入 3

1 3
3 3 3
0 1 2

输出 3

0 1 2