AT_abc128_e [ABC128E] Roadwork

[problemUrl]: https://atcoder.jp/contests/abc128/tasks/abc128_e 東西に無限に続く $ 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 $ を出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \leq\ N,\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ S_i\