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

输入按以下格式从标准输入给出。 > $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 翻译