配点 : $500$ 点

問題文

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

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

$Q$ 人の人が座標 $0$ に立っています。 $i$ 番目の人は時刻 $D_i$ に座標 $0$ を出発し、速度 $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$
• $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$ 番目の人が進む距離を出力せよ。 ただし $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

$1$ 番目の人は時刻 $0$ に座標 $0$ を出発し、時刻 $2$ に座標 $2$ に到着した時点で、$1$ 番目の道路工事による通行止めによって歩くのをやめます。

$2$ 番目の人は時刻 $1$ に座標 $0$ を出発し、時刻 $3$ に座標 $2$ に到着します。この時、$1$ 番目の道路工事は既に終了していますが、$4$ 番目の道路工事が始まっているため、同様に座標 $2$ で歩くのをやめます。

$4$ 番目および $6$ 番目の人は、歩いている最中に通行止めに出くわさないため、無限に歩き続けます。