问题 O: 道路工程

内存限制:128 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:168 解决:49

题目描述

有一条从西到东的无限长的街道,我们认为这是一条无限长的数轴
这条街上计划进行N项道路工程。
第i个道路工程在坐标Xi处阻段该点 阻挡的时间从Si - 0.5 到 Ti - 0.5
也就是说在 Si - 0.5 到 Ti - 0.5 这段时间内 Xi 这个点不能通过
第i个人将在时间Di开始从坐标0 , 不断以速度1个单位每秒正向行走,到达阻段点时停止行走。
求出每个人将要走的距离
如果这个人走的过程中不会遇到阻断点
则输出-1
1 <= N , Q <= 2e5 (200000)
0 <= Si < Ti <= 1e9 (1000000000)
1 <= Xi <= 1e9
0 <= D1 < D2 < D3 < ....... < Dq <= 1e9


输入

N Q
S1 T1 X1
S2 T2 X2
...........
Sn Tn Xn
D1
D2
.....
Dq

输出

每行一个数
输出第i个人将要走的距离
如果这个人走的过程中不会遇到阻断点
则输出-1

样例输入 复制

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

样例输出 复制

2
2
10
-1
13
-1