AT_abc342_e [ABC342E] Last Train

[problemUrl]: https://atcoder.jp/contests/abc342/tasks/abc342_e AtCoder 国には駅 $ 1, $ 駅 $ 2,\ldots, $ 駅 $ N $ の $ N $ 個の駅があります。 AtCoder 国に存在する電車の情報が $ M $ 個与えられます。 $ i $ 番目 $ (1\leq\ i\leq\ M) $ の情報は正整数の $ 6 $ つ組 $ (l\ _\ i,d\ _\ i,k\ _\ i,c\ _\ i,A\ _\ i,B\ _\ i) $ で表され、次のような情報に対応しています。 - $ t=l\ _\ i,l\ _\ i+d\ _\ i,l\ _\ i+2d\ _\ i,\ldots,l\ _\ i+(k\ _\ i-1)d\ _\ i $ それぞれについて、次のような電車が存在する。 - 時刻 $ t $ に 駅 $ A\ _\ i $ を出発し、時刻 $ t+c\ _\ i $ に駅 $ B\ _\ i $ に到着する。 これらの情報にあてはまらない電車は存在せず、電車以外の方法である駅から異なる駅へ移動することはできません。 また、乗り換えにかかる時間は無視できるとします。 駅 $ S $ から駅 $ N $ に到着できる最終時刻を $ f(S) $ とします。 より厳密には、整数の $ 4 $ つ組の列 $ \big((t\ _\ i,c\ _\ i,A\ _\ i,B\ _\ i)\big)\ _\ {i=1,2,\ldots,k} $ であって、次のすべての条件を満たすものが存在するような $ t $ の最大値を $ f(S) $ とします。 - $ t\leq\ t\ _\ 1 $ - $ A\ _\ 1=S,B\ _\ k=N $ - すべての $ 1\leq\ i\lt\ k $ について、$ B\ _\ i=A\ _\ {i+1} $ - すべての $ 1\leq\ i\leq\ k $ について、時刻 $ t\ _\ i $ に駅 $ A\ _\ i $ を出発して時刻 $ t\ _\ i+c\ _\ i $ に駅 $ B\ _\ i $ に到着する電車が存在する。 - すべての $ 1\leq\ i\lt\ k $ について、$ t\ _\ i+c\ _\ i\leq\ t\ _\ {i+1} $ ただし、そのような $ t $ が存在しないとき $ f(S)=-\infty $ とします。 $ f(1),f(2),\ldots,f(N-1) $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ l\ _\ 1 $ $ d\ _\ 1 $ $ k\ _\ 1 $ $ c\ _\ 1 $ $ A\ _\ 1 $ $ B\ _\ 1 $ $ l\ _\ 2 $ $ d\ _\ 2 $ $ k\ _\ 2 $ $ c\ _\ 2 $ $ A\ _\ 2 $ $ B\ _\ 2 $ $ \vdots $ $ l\ _\ M $ $ d\ _\ M $ $ k\ _\ M $ $ c\ _\ M $ $ A\ _\ M $ $ B\ _\ M $

$ N-1 $ 行出力せよ。 $ k $ 行目には $ f(k)\neq-\infty $ ならば $ f(k) $ を、$ f(k)=-\infty $ ならば `Unreachable` を出力せよ。

### 制約 - $ 2\leq\ N\leq2\times10\ ^\ 5 $ - $ 1\leq\ M\leq2\times10\ ^\ 5 $ - $ 1\leq\ l\ _\ i,d\ _\ i,k\ _\ i,c\ _\ i\leq10\ ^\ 9\ (1\leq\ i\leq\ M) $ - $ 1\leq\ A\ _\ i,B\ _\ i\leq\ N\ (1\leq\ i\leq\ M) $ - $ A\ _\ i\neq\ B\ _\ i\ (1\leq\ i\leq\ M) $ - 入力はすべて整数 ### Sample Explanation 1 AtCoder 国に走っている電車は以下の図のようになります（発着時間の情報は図には含まれていません）。 !\[\](https://img.atcoder.jp/abc342/c3007f6fd6e6bffff5483312395e51f6.png) 駅 $ 2 $ から駅 $ 6 $ に到着できる最終時刻について考えます。 次の図のように、駅 $ 2 $ を時刻 $ 56 $ に出発して駅 $ 2\rightarrow $ 駅 $ 3\rightarrow $ 駅 $ 4\rightarrow $ 駅 $ 6 $ のように移動することで駅 $ 6 $ に到着することができます。 !\[\](https://img.atcoder.jp/abc342/bf9e3c0a042ef63f63e45fd5b94a23af.png) 駅 $ 2 $ を時刻 $ 56 $ より遅く出発して駅 $ 6 $ に到着することはできないため、$ f(2)=56 $ です。 ### Sample Explanation 2 駅 $ 1 $ を時刻 $ 10\ ^\ {18} $ に出発して駅 $ 5 $ に時刻 $ 10\ ^\ {18}+10\ ^\ 9 $ に到着するような電車が存在します。それ以降に駅 $ 1 $ を出発する電車はないため、$ f(1)=10\ ^\ {18} $ です。 このように、答えが $ 32\operatorname{bit} $ 整数におさまらない場合もあります。 また、時刻 $ 14 $ に駅 $ 2 $ を出発して時刻 $ 20 $ に駅 $ 3 $ に到着するような電車は $ 2 $ 番目の情報と $ 3 $ 番目の情報の両方で存在が保証されています。 このように、複数の情報に重複している電車もあります。