E - 道路施工

得分：500分

问题描述

有一条无限长的街道，从西到东延伸，我们将其视为一条数轴。

在这条街道上安排了$N$次道路施工。 第$i$次道路施工会在时间$S_i - 0.5$到时间$T_i - 0.5$期间，阻塞坐标为$X_i$的点。

有$Q$个人站在坐标$0$处。第$i$个人将从时间$D_i$开始，在正向方向以速度$1$继续向前行走，当到达被阻塞的点时停止行走。

找出每个$Q$个人的行走距离。

约束

• 所有输入值均为整数。
• $1 \leq N, Q \leq 2 \times 10^5$
• $0 \leq S_i < T_i \leq 10^9$
• $1 \leq X_i \leq 10^9$
• $0 \leq D_1 < D_2 < ... < D_Q \leq 10^9$
• 如果 $i \neq j$ 并且 $X_i = X_j$，那么区间$[S_i, T_i)$和$[S_j, T_j)$不重叠。

输入

从标准输入获取输入数据，格式如下：

$N$ $Q$

$S_1$ $T_1$ $X_1$

$:$

$S_N$ $T_N$ $X_N$

$D_1$

$:$

$D_Q$

输出

输出$Q$行。第$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

第一个人从时间$0$开始在坐标$0$处行走，当到达第一个道路施工在时间$2$的阻塞点（坐标$2$）时停止行走。

第二个人从时间$1$开始在坐标$0$处行走，当到达坐标$2$时，第一次道路施工已经结束，但第四次道路施工开始，所以该人也停止在坐标$2$处行走。

第四个和第六个人在行走时没有遇到任何道路施工，所以他们将无限行走。这些情况下的输出为$-1$。