题目描述

There is an infinitely long street that runs west to east, which we consider as a number line.

There are $N$ roadworks scheduled on this street. The $i$-th roadwork blocks the point at coordinate $X_i$ from time $S_i - 0.5$ to time $T_i - 0.5$.

$Q$ people are standing at coordinate $0$. The $i$-th person will start the coordinate $0$ at time $D_i$, continue to walk with speed $1$ in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the $Q$ people will walk.

有一条自西向东的无限长的街道，我们把它看作一条数线。

这条街上有 $N$ 项道路工程。从时间 $S_i - 0.5$ 到时间 $T_i - 0.5$ ， $i$ -th 的道路工程挡住了坐标 $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$ （个）人行走的距离，或者 $-1$ （个）人永远行走的距离。

样例 #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

说明

数据规模与约定

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

样例 $1$ 解释

第一个人在时间 $0$ 从坐标 $0$ 开始行走，在时间 $2$ 到达被第一个道路工程阻挡的点时，在坐标 $2$ 处停止行走。

第二个人在时间 $1$ 从坐标 $0$ 开始行走，在时间 $3$ 到达坐标 $2$ 。第一项道路工程已经结束，但第四项道路工程已经开始，因此这个人也在坐标 $2$ 处停止行走。

第四个人和第六个人在行走过程中没有遇到任何道路施工，因此他们一直行走。这些情况的输出结果为 $-1$ 。