题目描述

位于 Ultima Thule 的公园内的一条双重观光道路是由以下原理工作：

1. 我们引入直角坐标系。
2. 在一些时刻会有 $2$ 个游客同时从点 $(-1,0)$ 和 $(1,0)$ 出发（去散步）。其中第一个人出发点 $(-1,0)$，第二个人出发点为 $(1,0)$。
3. 每一对游客都以相同的速度 $1$ 行动（每秒前进单位长度）。第一个人沿直线 $x=-1$，第二个人沿直线 $x=1$ 行动。他们都向 $y$ 轴正方向移动。
4. 在一些时刻墙会出现。墙 $(l_i,r_i)$ 是一条在点 $(0,l_i)$ 和 $(0,r_i)$ 之间的线段。每个墙都瞬间出现。

Ultima Thule 官方想要了解对于每一对同时出发的游客，他们将会有多长时间无法彼此望见？两个游客不能看到对方当且仅当他们位置的连线与至少一面墙相交。两条线段相交是指他们至少有一个公共点。我们假定线段的端点属于这条线段。

帮助他们计算所要求的时间。注意墙可以相交（以任何方式）或重合。

输入格式

第一行包含两个空格隔开的整数 $n,m$——游客的对数和墙的数目。

接下来 $m$ 行每行三个空格隔开的整数 $l_i,r_i,t_i$——墙的两端和出现的时间。

最后一行包含 $n$ 个严格递增、空格隔开的整数 $q_1,q_2,\dots,q_n$——每对游客出发的时刻。

输出格式

对每对游客输出一行一个整数——这对游客不能相互看见的时间是几秒。按照读入游客出发时间的顺序输出答案。

样例 #1

2 2
1 4 3
3 6 5
0 1

2
4

样例 #2

3 3
0 3 4
0 1 2
2 4 0
1 3 4

2
4
4

数据规模与约定

对于 $100\%$ 的数据：$1\le n,m\le 10^5$，$0\le l_i<r_i\le 10^9$，$0\le t_i\le 10^9$，$0\le q_i\le 10^9$。