题目描述

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

在这条街道上安排了 $N$ 次道路施工。第 $i$ 次施工会从时间 $S_i - 0.5$ 到时间 $T_i - 0.5$ 封锁坐标 $X_i$ 处的位置。

有 $Q$ 个人站在坐标 $0$ 处。第 $i$ 个人将从时间 $D_i$ 开始在坐标 $0$ 处出发，沿正方向以速度 $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$。

示例输入1

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

示例输出1

2
2
10
-1
13
-1

第一个人从时间 $0$ 开始，以速度 $1$ 行走，当达到被第一次施工封锁的位置时，在时间 $2$ 停止行走。

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

第四个和第六个人在行走过程中没有遇到道路施工，所以他们将永远行走。对于这些情况的输出是 $-1$。