You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC128E] Roadwork

题目描述

一共有 $n$ 个工程，第 $i$ 个工程在 $X_i$ 位置施工，施工时间是 $[S_i,T_i)$。

一共 $m$ 个人，均从位置 $0$ 出发。

第 $i$ 个人在 $D_i$ 时刻出发，每秒走 $1$ 个单位长度。如果当前位置正在施工，则停下。

你需要求出每个人停下的位置，如果可以一直走下去，输出 $-1$。

输入格式

输入格式如下。第一行两个整数 $N,Q$ ，接下来 $N$ 行，每行三个整数 $S_i,T_i,X_i$ ，再接下来 $Q$ 行，每行一个整数 $D_i$ 。

$N$ $Q$ $S_1$ $T_1$ $X_1$ $:$ $S_N$ $T_N$ $X_N$ $D_1$ $:$ $D_Q$

输出格式

输出共 $Q$ 行。第 $i$ 行表示第 $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\ <\ T_i\ \leq\ 10^9$
• $1\ \leq\ X_i\ \leq\ 10^9$
• $0\ \leq\ D_1\ <\ D_2\ <\ ...\ <\ D_Q\ \leq\ 10^9$
• $i\ \neq\ j$ 且 $X_i\ =\ X_j$ 时、区间 $[S_i,\ T_i)$ 和 $[S_j,\ T_j)$ 不相交