分数: 500 点
问题陈述
有一条从西向东无限长的街道,我们将其视为数轴。
有 N 这条街道上计划进行道路施工。 的 i第一个道路施工阻挡了坐标处的点 X_i 从时间 S_i - 0.5 到时间 T_i - 0.5.
Q 人们正站在坐标处 0。的 i第人将开始坐标 0 时间 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
- If 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 时间 0 并在坐标处停止行走 2 当到达第一个道路施工所阻挡的点时 2.
第二人开始坐标 0 时间 1 并到达坐标 2 时间 3。第一个道路施工已经结束,但是第四个道路施工已经开始,所以这个人也在坐标处停止行走 2.
第四个人和第六个人在行走时没有遇到道路施工,因此他们永远行走。这些情况的输出是 -1.