道路施工

题目描述

有一条东西向无限延伸的大街,可以看作一条数轴。

在这条大街上要进行 $N$ 次道路施工。第 $i$ 次施工从时刻 $S_i - 0.5$ 到时刻 $T_i - 0.5$,把坐标 $X_i$ 封锁通行。

有 $Q$ 个人站在坐标 $0$ 处。第 $i$ 个人在时刻 $D_i$ 从坐标 $0$ 出发,以速度 $1$ 向正方向一直走下去。如果在行走途中到达了正在封锁通行的地点,就在那里停下。

求这 $Q$ 个人各自前进的距离。

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$S_1$ $T_1$ $X_1$
$:$
$S_N$ $T_N$ $X_N$
$D_1$
$:$
$D_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 个人前进的距离。 不过,如果第 $i$ 个人会无限地走下去,则输出 $-1$ 代替。

样例

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

2
2
10
-1
13
-1

第 $1$ 个人在时刻 $0$ 从坐标 $0$ 出发,在时刻 $2$ 到达坐标 $2$ 时,因第 $1$ 次道路施工的封锁而停下。

第 $2$ 个人在时刻 $1$ 从坐标 $0$ 出发,在时刻 $3$ 到达坐标 $2$。此时第 $1$ 次道路施工已经结束,但第 $4$ 次道路施工已经开始,因此同样在坐标 $2$ 处停下。

第 $4$ 和第 $6$ 个人在行走途中没有遇到封锁,因此会无限地走下去。

数据范围

• 输入均为整数
• $1 \le N, Q \le 2 \times 10^5$
• $0 \le S_i \lt T_i \le 10^9$
• $1 \le X_i \le 10^9$
• $0 \le D_1 \lt D_2 \lt ... \lt D_Q \le 10^9$
• 当 $i \neq j$ 且 $X_i = X_j$ 时,区间 $[S_i, T_i)$ 与区间 $[S_j, T_j)$ 不重叠