AT_abc368_e [ABC368E] Train Delay

[problemUrl]: https://atcoder.jp/contests/abc368/tasks/abc368_e Atcoder 国には $ 1 $ から $ N $ の番号がついた $ N $ 個の街と、$ 1 $ から $ M $ の番号がついた $ M $ 本の電車が走っています。 電車 $ i $ は街 $ A_i $ を時刻 $ S_i $ に発車し、街 $ B_i $ に時刻 $ T_i $ に到着します。 正の整数 $ X_1 $ が与えられるので、$ 0 $ 以上の整数 $ X_2,\ldots,X_M $ を以下の条件を満たすように定める方法のうち、$ X_2+\ldots+X_M $ が最小になるものを求めてください。 - 条件：$ 1\ \leq\ i,j\ \leq\ M $ を満たす全ての組 $ (i,j) $ について、「$ B_i=A_j $ かつ $ T_i\ \leq\ S_j $」ならば「$ T_i+X_i\ \leq\ S_j+X_j $」 - すなわち、もともと乗り換え可能だった電車の組は、各電車 $ i $ の発車時刻・到着時刻を $ X_i $ 遅らせても乗り換え可能である なお、$ X_2+\ldots+X_M $ が最小になるような $ X_2,\ldots,X_M $ の定め方は一意であることが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ A_1 $ $ B_1 $ $ S_1 $ $ T_1 $ $ \vdots $ $ A_M $ $ B_M $ $ S_M $ $ T_M $

条件を満たし、和を最小化するような $ X_2,\ldots,X_M $ を、この順に空白区切りで出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 2\ \leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i,B_i\ \leq\ N $ - $ A_i\ \neq\ B_i $ - $ 0\ \leq\ S_i\