末班列车

题目描述

在 AtCoder 国中,有 $N$ 个车站:车站 $1$,车站 $2$,$\ldots$,车站 $N$。

给你关于该国列车的 $M$ 条信息。第 $i$ 条信息 $(1\le i\le 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$ 从车站 $A_i$ 出发,在时刻 $t+c_i$ 到达车站 $B_i$。

除这些信息所描述的列车以外不存在其他列车,并且除乘坐列车以外,无法以任何方式从一个车站移动到另一个车站。

另外,假设换乘所需的时间可以忽略不计。

设 $f(S)$ 为从车站 $S$ 出发能到达车站 $N$ 的最晚时刻。

更精确地说,$f(S)$ 定义为满足以下所有条件的四整数元组序列 $\big((t_i,c_i,A_i,B_i)\big)_{i=1,2,\ldots,k}$ 存在时的最大 $t$ 值：

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

样例

6 7
10 5 10 3 1 3
13 5 10 2 3 4
15 5 10 7 4 6
3 10 2 4 2 5
7 10 2 3 5 6
5 3 18 2 2 3
6 3 20 4 2 1

55
56
58
60
17

考虑从车站 $2$ 出发能到达车站 $6$ 的最晚时刻。如下所示,可以在时刻 $56$ 从车站 $2$ 出发,按车站 $2\rightarrow$ 车站 $3\rightarrow$ 车站 $4\rightarrow$ 车站 $6$ 的顺序移动,从而到达车站 $6$。

无法在时刻 $56$ 之后从车站 $2$ 出发并到达车站 $6$,所以 $f(2)=56$。

5 5
1000000000 1000000000 1000000000 1000000000 1 5
5 9 2 6 2 3
10 4 1 6 2 3
1 1 1 1 3 5
3 1 4 1 5 1

1000000000000000000
Unreachable
1
Unreachable

存在一列在时刻 $10^{18}$ 从车站 $1$ 出发、在时刻 $10^{18}+10^9$ 到达车站 $5$ 的列车。在此之后没有从车站 $1$ 出发的列车,所以 $f(1)=10^{18}$。 由此可见,答案可能超出 $32\operatorname{bit}$ 整数的范围。

另外,第 2 条和第 3 条信息都保证了存在一列在时刻 $14$ 从车站 $2$ 出发、在时刻 $20$ 到达车站 $3$ 的列车。 由此可见,有些列车可能出现在多条信息中。

16 20
4018 9698 2850 3026 8 11
2310 7571 7732 1862 13 14
2440 2121 20 1849 11 16
2560 5115 190 3655 5 16
1936 6664 39 8822 4 16
7597 8325 20 7576 12 5
5396 1088 540 7765 15 1
3226 88 6988 2504 13 5
1838 7490 63 4098 8 3
1456 5042 4 2815 14 7
3762 6803 5054 6994 10 9
9526 6001 61 8025 7 8
5176 6747 107 3403 1 5
2014 5533 2031 8127 8 11
8102 5878 58 9548 9 10
3788 174 3088 5950 3 13
7778 5389 100 9003 10 15
556 9425 9458 109 3 11
5725 7937 10 3282 2 9
6951 7211 8590 1994 15 12

720358
77158
540926
255168
969295
Unreachable
369586
466218
343148
541289
42739
165772
618082
16582
591828

数据范围

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $1\le l_i,d_i,k_i,c_i\le 10^9\ (1\le i\le M)$
• $1\le A_i,B_i\le N\ (1\le i\le M)$
• $A_i\neq B_i\ (1\le i\le M)$
• 所有输入值均为整数。