{"problem":{"name":"Last Train","description":{"content":"In the country of AtCoder, there are $N$ stations: station $1$, station $2$, $\\ldots$, station $N$. You are given $M$ pieces of information about trains in the country. The $i$\\-th piece of informatio","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc342_e"},"statements":[{"statement_type":"Markdown","content":"In the country of AtCoder, there are $N$ stations: station $1$, station $2$, $\\ldots$, station $N$.\nYou are given $M$ pieces of information about trains in the country. The $i$\\-th piece of information $(1\\leq i\\leq M)$ is represented by a tuple of six positive integers $(l _ i,d _ i,k _ i,c _ i,A _ i,B _ i)$, which corresponds to the following information:\n\n*   For each $t=l _ i,l _ i+d _ i,l _ i+2d _ i,\\ldots,l _ i+(k _ i-1)d _ i$, there is a train as follows:\n    *   The train departs from station $A _ i$ at time $t$ and arrives at station $B _ i$ at time $t+c _ i$.\n\nNo trains exist other than those described by this information, and it is impossible to move from one station to another by any means other than by train.  \nAlso, assume that the time required for transfers is negligible.\nLet $f(S)$ be the latest time at which one can arrive at station $N$ from station $S$.  \nMore precisely, $f(S)$ is defined as the maximum value of $t$ for which there is a sequence of tuples of four integers $\\big((t _ i,c _ i,A _ i,B _ i)\\big) _ {i=1,2,\\ldots,k}$ that satisfies all of the following conditions:\n\n*   $t\\leq t _ 1$\n*   $A _ 1=S,B _ k=N$\n*   $B _ i=A _ {i+1}$ for all $1\\leq i\\lt k$,\n*   For all $1\\leq i\\leq k$, there is a train that departs from station $A _ i$ at time $t _ i$ and arrives at station $B _ i$ at time $t _ i+c _ i$.\n*   $t _ i+c _ i\\leq t _ {i+1}$ for all $1\\leq i\\lt k$.\n\nIf no such $t$ exists, set $f(S)=-\\infty$.\nFind $f(1),f(2),\\ldots,f(N-1)$.\n\n## Constraints\n\n*   $2\\leq N\\leq2\\times10 ^ 5$\n*   $1\\leq M\\leq2\\times10 ^ 5$\n*   $1\\leq l _ i,d _ i,k _ i,c _ i\\leq10 ^ 9\\ (1\\leq i\\leq M)$\n*   $1\\leq A _ i,B _ i\\leq N\\ (1\\leq i\\leq M)$\n*   $A _ i\\neq B _ i\\ (1\\leq i\\leq M)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$l _ 1$ $d _ 1$ $k _ 1$ $c _ 1$ $A _ 1$ $B _ 1$\n$l _ 2$ $d _ 2$ $k _ 2$ $c _ 2$ $A _ 2$ $B _ 2$\n$\\vdots$\n$l _ M$ $d _ M$ $k _ M$ $c _ M$ $A _ M$ $B _ M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc342_e","tags":[],"sample_group":[["6 7\n10 5 10 3 1 3\n13 5 10 2 3 4\n15 5 10 7 4 6\n3 10 2 4 2 5\n7 10 2 3 5 6\n5 3 18 2 2 3\n6 3 20 4 2 1","55\n56\n58\n60\n17\n\nThe following diagram shows the trains running in the country (information about arrival and departure times is omitted).\n![image](https://img.atcoder.jp/abc342/c3007f6fd6e6bffff5483312395e51f6.png)\nConsider the latest time at which one can arrive at station $6$ from station $2$. As shown in the following diagram, one can arrive at station $6$ by departing from station $2$ at time $56$ and moving as station $2\\rightarrow$ station $3\\rightarrow$ station $4\\rightarrow$ station $6$.\n![image](https://img.atcoder.jp/abc342/b6667844f8166458430c27bd93838a76.png)\nIt is impossible to depart from station $2$ after time $56$ and arrive at station $6$, so $f(2)=56$."],["5 5\n1000000000 1000000000 1000000000 1000000000 1 5\n5 9 2 6 2 3\n10 4 1 6 2 3\n1 1 1 1 3 5\n3 1 4 1 5 1","1000000000000000000\nUnreachable\n1\nUnreachable\n\nThere is a train that departs from station $1$ at time $10 ^ {18}$ and arrives at station $5$ at time $10 ^ {18}+10 ^ 9$. There are no trains departing from station $1$ after that time, so $f(1)=10 ^ {18}$. As seen here, the answer may not fit within a $32\\operatorname{bit}$ integer.\nAlso, both the second and third pieces of information guarantee that there is a train that departs from station $2$ at time $14$ and arrives at station $3$ at time $20$. As seen here, some trains may appear in multiple pieces of information."],["16 20\n4018 9698 2850 3026 8 11\n2310 7571 7732 1862 13 14\n2440 2121 20 1849 11 16\n2560 5115 190 3655 5 16\n1936 6664 39 8822 4 16\n7597 8325 20 7576 12 5\n5396 1088 540 7765 15 1\n3226 88 6988 2504 13 5\n1838 7490 63 4098 8 3\n1456 5042 4 2815 14 7\n3762 6803 5054 6994 10 9\n9526 6001 61 8025 7 8\n5176 6747 107 3403 1 5\n2014 5533 2031 8127 8 11\n8102 5878 58 9548 9 10\n3788 174 3088 5950 3 13\n7778 5389 100 9003 10 15\n556 9425 9458 109 3 11\n5725 7937 10 3282 2 9\n6951 7211 8590 1994 15 12","720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828"]],"created_at":"2026-03-03 11:01:14"}}