← 返回题目列表

AtCoder · abc128_e

E. 道路施工

中文机器翻译题面 查看原题

分数: 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.