AT_abc128_e [ABC128E] Roadwork

有一条东西方向无限延伸的大道，可以看作是一条数轴。 在这条大道上将进行 $N$ 次道路施工。第 $i$ 次道路施工会在时刻 $S_i - 0.5$ 到时刻 $T_i - 0.5$ 期间，使坐标 $X_i$ 处禁止通行。 有 $Q$ 个人站在坐标 $0$ 处。第 $i$ 个人会在时刻 $D_i$ 从坐标 $0$ 出发，以速度 $1$ 向正方向一直行走。如果在行走过程中到达了正在禁止通行的坐标，则会在该处停止行走。 请计算每个人能够前进的距离。如果某个人可以无限行走下去，则输出 $-1$。

输入通过标准输入按以下格式给出。 > $N$ $Q$ > $S_1$ $T_1$ $X_1$ > $\vdots$ > $S_N$ $T_N$ $X_N$ > $D_1$ > $\vdots$ > $D_Q$

输出共 $Q$ 行。 第 $i$ 行输出第 $i$ 个人能够前进的距离。如果第 $i$ 个人可以无限行走，则输出 $-1$。

### 限制条件 - 所有输入均为整数。 - $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 < \cdots < D_Q \leq 10^9$ - 若 $i \neq j$ 且 $X_i = X_j$，则区间 $[S_i, T_i)$ 与区间 $[S_j, T_j)$ 不重叠。 ### 样例解释 1 第 $1$ 个人在时刻 $0$ 从坐标 $0$ 出发，在时刻 $2$ 到达坐标 $2$ 时，由于第 $1$ 次道路施工导致该处禁止通行，因此停止行走。第 $2$ 个人在时刻 $1$ 从坐标 $0$ 出发，在时刻 $3$ 到达坐标 $2$。此时第 $1$ 次道路施工已结束，但第 $4$ 次道路施工已经开始，因此同样在坐标 $2$ 停止行走。第 $4$ 个人和第 $6$ 个人在行走过程中不会遇到任何禁止通行的点，因此可以无限行走。 由 ChatGPT 4.1 翻译