AT_abc342_e.[ABC342E] Last Train

AtCoder 国有 $N$ 个车站，分别为车站 $1$、车站 $2$、……、车站 $N$。

AtCoder 国中存在 $M$ 条列车信息。第 $i$ 条信息（$1\leq i\leq M$）由六个正整数 $(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$，都有如下列车：
  • 在时刻 $t$ 从车站 $A_i$ 出发，在时刻 $t+c_i$ 到达车站 $B_i$。

除此之外，不存在其他列车，也无法通过其他方式从一个车站移动到另一个不同的车站。
此外，换乘所需时间可以忽略不计。

定义从车站 $S$ 到达车站 $N$ 的最晚出发时刻为 $f(S)$。
更严格地说，$f(S)$ 是满足以下所有条件的整数四元组序列 $\big((t_i, c_i, A_i, B_i)\big)_{i=1,2,\ldots,k}$ 中 $t$ 的最大值：

• $t\leq t_1$
• $A_1=S, B_k=N$
• 对所有 $1\leq i<k$，有 $B_i=A_{i+1}$
• 对所有 $1\leq i\leq k$，存在在时刻 $t_i$ 从车站 $A_i$ 出发、在时刻 $t_i+c_i$ 到达车站 $B_i$ 的列车
• 对所有 $1\leq i<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)$，否则输出 Unreachable。

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 2\times 10^5$
• $1\leq l_i, d_i, k_i, c_i\leq 10^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)$
• 输入均为整数

样例解释 1

AtCoder 国中运行的列车如下图所示（图中未包含发车和到达时间信息）。

以车站 $2$ 到车站 $6$ 的最晚到达时刻为例。如下图所示，可以在时刻 $56$ 从车站 $2$ 出发，依次经过车站 $2\rightarrow 3\rightarrow 4\rightarrow 6$ 到达车站 $6$。

无法在时刻 $56$ 之后从车站 $2$ 出发到达车站 $6$，因此 $f(2)=56$。

样例解释 2

存在一列在时刻 $10^{18}$ 从车站 $1$ 出发、在时刻 $10^{18}+10^9$ 到达车站 $5$ 的列车。此后没有更晚出发的列车，因此 $f(1)=10^{18}$。
另外，在时刻 $14$ 从车站 $2$ 出发、在时刻 $20$ 到达车站 $3$ 的列车，既由第 $2$ 条信息，也由第 $3$ 条信息保证存在。
如上所述，可能存在多条信息重复描述同一列车。

由 ChatGPT 4.1 翻译