AT_abc414_g [ABC414G] AtCoder Express 4

AtCoder 王国には東西に伸びる路線があり、この路線には駅 $ 1,2,\ldots,N $ があります。駅 $ i\ (1\leq i\leq N) $ は座標 $ x_i $ に位置しています $ (x_1 < x_2 < \ldots < x_N) $ 。 この路線で AtCoder Express 社は $ M $ 種類の特急列車を運行しています。 $ i $ 種類目の特急列車は以下のように運行されます。 - 乗車できる駅は駅 $ l_i,l_i+1,\ldots,r_i $ のいずれかである。 - 降車できる駅は駅 $ L_i, L_i+1, \ldots, R_i $ のいずれかである。ここで、列車の進行方向は東西のどちらか一方向であり、 $ r_i\lt L_i $ または $ R_i\lt l_i $ のいずれかが成り立つ。 - 運賃は、初乗り運賃として $ c_i $ がかかり、乗車駅から降車駅までの距離に応じた金額が加算される。具体的には、駅 $ s\ (l_i\leq s\leq r_i) $ から駅 $ t\ (L_i\leq t\leq R_i) $ まで移動する場合の運賃は $ c_i+|x_s-x_t| $ である。 あなたはいま駅 $ 1 $ にいます。各 $ k\ (2\leq k\leq N) $ について、特急列車を乗り継いで駅 $ 1 $ から駅 $ k $ まで移動することができるかどうか判定し、移動できるならば移動するために必要な運賃の合計の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ x_1 $ $ x_2 $ $ \ldots $ $ x_N $ $ l_1 $ $ r_1 $ $ L_1 $ $ R_1 $ $ c_1 $ $ l_2 $ $ r_2 $ $ L_2 $ $ R_2 $ $ c_2 $ $ \vdots $ $ l_M $ $ r_M $ $ L_M $ $ R_M $ $ c_M $

答えを以下の形式で出力せよ。 > $ \mathrm{ans}_2 $ $ \mathrm{ans}_3 $ $ \ldots $ $ \mathrm{ans}_N $ $ \mathrm{ans}_i $ は $ k=i $ に対する答えである。駅 $ 1 $ から駅 $ i $ まで移動できる場合は移動に必要な運賃の合計の最小値を、移動できない場合は `-1` とせよ。

### Sample Explanation 1 駅 $ 2 $ には以下のようにして移動することができます。 1. $ 1 $ 種類目の特急列車に駅 $ 1 $ から乗車して駅 $ 6 $ で降車する。運賃は $ c_1+|x_1-x_6|=100+|0-150|=250 $ である。 2. $ 3 $ 種類目の特急列車に駅 $ 6 $ から乗車して駅 $ 2 $ で降車する。運賃は $ c_3+|x_6-x_2|=30+|150-20|=160 $ である。 このときの運賃の合計は $ 410 $ で、これが最小です。 駅 $ 4 $ には移動することができません。 ### Constraints - $ 2\leq N\leq 10^5 $ - $ 1\leq M\leq 10^5 $ - $ 0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12} $ - $ 1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N $ - $ r_i\lt L_i $ または $ R_i\lt l_i $ のいずれかが成り立つ - $ 1\leq c_i\leq 10^{12} $ - 入力は全て整数