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.

题目背景

在北辰学校, 有一条鲜花大道, 路上种满了各种各样的花朵, 每朵花都会有一个花期, 鼠鼠们喜欢赏花.

题目描述

在鲜花大道上, 一共有 $m$ 盆花, 每朵花都有一个花期 $[l, r)$ , 以及一个坐标 $x$ .

注意: 区间是半闭半开的.

有 $n$ 名鼠鼠要去赏花, 从坐标 $0$ 点出发, 鼠鼠的步行速度是 $1$ , 每个鼠鼠都有一个出发时间 $d_i$ .

如果鼠鼠在步行过程中遇到了某朵花开, 就会停下脚步, 否则就会一直向后步行.

求每名鼠鼠第一次停下脚步的位置, 如果这名可怜的鼠鼠无法遇到开花, 则输出 -1 .

数据格式

输入格式

第一行两个整数 $m, n$ .

接下来 $m$ 行, 每行三个整数 $l_i, r_i, x_i$ 表示第$i$朵花的花期和位置.

接下来 $n$ 行, 每行一个整数 $d_i$ 表示第 $i$ 名鼠鼠的出发时刻.

输出格式

输出 $n$ 行, 没行一个整数表示第 $i$ 名鼠鼠遇到的第一朵花开的位置, 如果无法遇到花开, 则输出 -1 .

样例

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

2
-1
13
10
-1
2

样例1解释

第1个人从0时刻出发, 时刻2步行到3号花位置, 此时3号花盛开, 则停在2位置赏花.

第2个人从8时刻出发, 步行过程中无法遇到任意一朵花开, 则输出-1

第3个人从5时刻出发, 在第18时刻, 步行到13位置, 此时第4朵花盛开, 则停留在13位置赏花.

数据范围

$1<= m, n<= 2*10^5$

$0 <=l_i <=r_i <= 10^9$

$1 <= x_i <= 10^9$

$0 <= d_i <= 10^9$

• $d_i$ 各不相同
• 在同一个位置的不同花的花期不重叠