题目描述

東西に無限に続く $1$ 本の大通りがあり、数直線とみなすことができます。

この大通り上で $N$ 回道路工事が行われます。 $i$ 番目の道路工事は時刻 $S_i\ -\ 0.5$ から時刻 $T_i\ -\ 0.5$ まで座標 $X_i$ を通行止めにします。

$Q$ 人の人が座標 $0$ に立っています。 $i$ 番目の人は時刻 $D_i$ に座標 $0$ を出発し、速度 $1$ で正の方向へ歩き続けます。 歩いている途中で通行止めとなっている地点に到達した場合には、そこで歩くのをやめます。

$Q$ 人それぞれが進む距離を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$Q$ 行出力せよ。

$i$ 行目には $i$ 番目の人が進む距離を出力せよ。 ただし $i$ 番目の人が無限に歩き続ける場合は、代わりに $-1$ を出力せよ。

题目大意

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

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

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

你需要求出每个人停下的位置，如果可以一直走下去，输出 $-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

提示

制約

• 入力は全て整数
• $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)$ は重ならない

Sample Explanation 1

$1$ 番目の人は時刻 $0$ に座標 $0$ を出発し、時刻 $2$ に座標 $2$ に到着した時点で、$1$ 番目の道路工事による通行止めによって歩くのをやめます。 $2$ 番目の人は時刻 $1$ に座標 $0$ を出発し、時刻 $3$ に座標 $2$ に到着します。この時、$1$ 番目の道路工事は既に終了していますが、$4$ 番目の道路工事が始まっているため、同様に座標 $2$ で歩くのをやめます。 $4$ 番目および $6$ 番目の人は、歩いている最中に通行止めに出くわさないため、無限に歩き続けます。