问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
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 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:

- 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:
- The train departs from station A _ i at time t and arrives at station B _ i at time t+c _ i.



No 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.
Also, assume that the time required for transfers is negligible.
Let f(S) be the latest time at which one can arrive at station N from station S.
More 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:

- t\leq t _ 1
- A _ 1=S,B _ k=N
- B _ i=A _ {i+1} for all 1\leq i\lt k,
- 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.
- t _ i+c _ i\leq t _ {i+1} for all 1\leq i\lt k.

If no such t exists, set f(S)=-\infty.
Find f(1),f(2),\ldots,f(N-1).

Input

The input is given from Standard Input in the following format:
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

Output

Print N-1 lines.
The k-th line should contain f(k) if f(k)\neq-\infty, and Unreachable if f(k)=-\infty.

Constraints


- 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)
- All input values are integers.

Sample Input 1

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

Sample Output 1

55
56
58
60
17

The following diagram shows the trains running in the country (information about arrival and departure times is omitted).

Consider 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.

It is impossible to depart from station 2 after time 56 and arrive at station 6, so f(2)=56.

Sample Input 2

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

Sample Output 2

1000000000000000000
Unreachable
1
Unreachable

There 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.
Also, 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.

Sample Input 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

Sample Output 3

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

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
from collections import defaultdict

def read_input():
input_lines = sys.stdin.readlines()
N, M = map(int, input_lines[0].split())
train_info = [list(map(int, line.split())) for line in input_lines[1:]]
return N, M, train_info

def solve(N, M, train_info):
trains = defaultdict(list)
for l, d, k, c, A, B in train_info:
for j in range(k):
t = l + j * d
trains[A].append((t, t + c, B))

f = [-float('inf')] * (N + 1)
f[N] = float('inf')

for i in range(N - 1, 0, -1):
for t, t_c, B in trains[i]:
if f[B] != -float('inf') and t_c <= f[B]:
f[i] = max(f[i], t)

return f

def print_results(f):
for i in range(1, len(f) - 1):
if f[i] == -float('inf'):
print("Unreachable")
else:
print(f[i])

def main():
N, M, train_info = read_input()
f = solve(N, M, train_info)
print_results(f)

if __name__ == "__main__":
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
deepseek-r1

```python
import heapq

def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1

adj_rev = [[] for _ in range(N+1)] # 1-based indexing

for _ in range(M):
l = int(data[idx])
d = int(data[idx+1])
k = int(data[idx+2])
c = int(data[idx+3])
A = int(data[idx+4])
B = int(data[idx+5])
idx += 6

adj_rev[B].append( (A, l, d, k, c) )

dist = [ -float('inf') ] * (N + 1)
dist[N] = 10**18

heap = []
heapq.heappush(heap, (-dist[N], N))

while heap:
current_neg, u = heapq.heappop(heap)
current_dist = -current_neg

if current_dist < dist[u]:
continue

for edge in adj_rev[u]:
A, l, d, k, c = edge
T = dist[u] - c

if T < l:
continue

m_max = (T - l) // d
m_max = min(m_max, k - 1)
if m_max < 0:
continue

t_candidate = l + m_max * d
if t_candidate > T:
continue

if t_candidate > dist[A]:
dist[A] = t_candidate
heapq.heappush(heap, (-dist[A], A))

for i in range(1, N):
if dist[i] == -float('inf'):
print("Unreachable")
else:
print(dist[i])

if __name__ == '__main__':
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
import math
import heapq

sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
N = int(N)
M = int(M)
from collections import defaultdict
import bisect

# Build reverse edges
adj = [[] for _ in range(N + 1)] # adj[s] = list of train patterns where B_i = s

for _ in range(M):
l_i, d_i, k_i, c_i, A_i, B_i = map(int, sys.stdin.readline().split())
adj[B_i].append((l_i, d_i, k_i, c_i, A_i))

import heapq

INF = 1 << 60 # Large enough number
f = [-INF] * (N + 1)
f[N] = INF # At destination N, we can arrive at any time

heap = [(-f[N], N)] # Max-heap by negative f[s] to get station with largest f[s]

while heap:
neg_fs, s = heapq.heappop(heap)
fs = -neg_fs
if f[s] < fs:
continue # Already updated to a larger f[s]
for pattern in adj[s]:
l_i, d_i, k_i, c_i, A_i = pattern

temp = f[s] - c_i - l_i
if temp < 0:
continue # No possible departure time from A_i via this train pattern
x_max = temp // d_i
x_max = min(x_max, k_i - 1)
if x_max < 0:
continue # No valid x_max
t_max = l_i + x_max * d_i
if t_max > f[A_i]:
f[A_i] = t_max
heapq.heappush(heap, (-f[A_i], A_i))

for S in range(1, N):
if f[S] == -INF:
print("Unreachable")
else:
print(int(f[S]))

if __name__ == '__main__':
threading.Thread(target=main).start()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
import heapq
from collections import defaultdict

def solve():
input = sys.stdin.read
data = input().split()

N = int(data[0])
M = int(data[1])

trains = defaultdict(list)

index = 2
for _ in range(M):
l = int(data[index])
d = int(data[index + 1])
k = int(data[index + 2])
c = int(data[index + 3])
A = int(data[index + 4])
B = int(data[index + 5])
index += 6

for i in range(k):
t = l + i * d
trains[A].append((t, c, B))

# Dijkstra-like approach to find the latest arrival time at station N
latest_arrival = [-float('inf')] * (N + 1)
latest_arrival[N] = float('inf')

# Priority queue to process stations by latest arrival time
pq = []
heapq.heappush(pq, (-float('inf'), N))

while pq:
current_time, station = heapq.heappop(pq)
current_time = -current_time

for t, c, next_station in trains[station]:
if t + c <= current_time:
if t > latest_arrival[next_station]:
latest_arrival[next_station] = t
heapq.heappush(pq, (-t, next_station))

# Output the results for stations 1 to N-1
results = []
for i in range(1, N):
if latest_arrival[i] == -float('inf'):
results.append("Unreachable")
else:
results.append(str(latest_arrival[i]))

print("\n".join(results))

```
 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from heapq import heappush, heappop
from collections import defaultdict

def main():
N, M = map(int, input().split())
trains = [tuple(map(int, input().split())) for _ in range(M)]

# Create a graph where edges represent possible train connections
graph = defaultdict(list)
for l, d, k, c, A, B in trains:
for i in range(k):
time = l + i * d
graph[A].append((time, time + c, B))

# Use Dijkstra's algorithm to find the latest arrival time for each station
latest_arrival = [-float('inf')] * N
latest_arrival[N-1] = float('inf')
queue = [(float('inf'), N-1)]

while queue:
time, station = heappop(queue)
if time <= latest_arrival[station]:
continue

for next_time, arrival_time, next_station in graph[station]:
if arrival_time <= latest_arrival[next_station]:
continue

latest_arrival[next_station] = min(latest_arrival[next_station], arrival_time)
heappush(queue, (next_time, next_station))

# Print the results
for i in range(N-1):
result = latest_arrival[i]
print(result if result != -float('inf') else 'Unreachable')

if __name__ == "__main__":
main()
```
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
import sys
from collections import defaultdict

# Read input
input_lines = sys.stdin.readlines()
N, M = map(int, input_lines[0].split())

# Parse the input
trains = []
for i in range(1, M + 1):
l, d, k, c, A, B = map(int, input_lines[i].split())
trains.append((l, d, k, c, A, B))

# Initialize the latest arrival times
latest_arrival = [-float('inf')] * N
latest_arrival[N - 1] = float('inf')

# Process each train information
for l, d, k, c, A, B in trains:
max_time = -float('inf')
for t in range(l, l + k * d + 1, d):
if t + c <= latest_arrival[B - 1]:
max_time = max(max_time, t + c)
latest_arrival[A - 1] = max(latest_arrival[A - 1], max_time)

# Output the results
for i in range(N - 1):
if latest_arrival[i] == -float('inf'):
print("Unreachable")
else:
print(latest_arrival[i])
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys
import heapq
from collections import defaultdict

def main():
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
l, d, k, c, A, B = map(int, input().split())
for t in range(l, l + k * d, d):
graph[A].append((t, c, B))

for i in range(1, N + 1):
graph[i].sort()

dist = [-float('inf')] * (N + 1)
dist[N] = float('inf')
pq = [(-float('inf'), N)]
while pq:
t, u = heapq.heappop(pq)
t = -t
if dist[u] != t:
continue
i = len(graph[u]) - 1
for v in range(1, N + 1):
if u == v:
continue
while i >= 0 and (graph[u][i][2] != v or graph[u][i][0] + graph[u][i][1] > t):
i -= 1
if i < 0:
continue
nt = graph[u][i][0]
if nt + graph[u][i][1] <= t and nt > dist[v]:
dist[v] = nt
heapq.heappush(pq, (-nt, v))

for i in range(1, N):
if dist[i] == -float('inf'):
print("Unreachable")
else:
print(dist[i])

if __name__ == '__main__':
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys
import heapq

def read_ints():
return map(int, sys.stdin.readline().split())

def read_int():
return int(sys.stdin.readline())

def solve():
n, m = read_ints()
graph = [[] for _ in range(n + 1)]
for _ in range(m):
l, d, k, c, a, b = read_ints()
for i in range(k):
t = l + i * d
graph[a].append((t, c, b))

dist = [-float('inf')] * (n + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
d, u = heapq.heappop(pq)
if d != dist[u]:
continue
for t, c, v in graph[u]:
if t + c > dist[u]:
continue
if dist[u] + c > dist[v]:
dist[v] = dist[u] + c
heapq.heappush(pq, (-dist[v], v))

for i in range(1, n):
if dist[i] < 0:
print("Unreachable")
else:
print(dist[i])

if __name__ == "__main__":
solve()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
baichuan4 ```python
import sys
from collections import defaultdict

def read_input():
N, M = map(int, sys.stdin.readline().split())
trains = []
for _ in range(M):
li, di, ki, ci, Ai, Bi = map(int, sys.stdin.readline().split())
for t in range(li, li + ki * di, di):
trains.append((t, t + ci, Ai, Bi))
return N, trains

def find_latest_arrival_time(N, trains):
graph = defaultdict(list)
for t, arr_t, start, end in trains:
graph[start].append((t, arr_t, end))

def dfs(station, current_time):
if station == N:
return current_time
for t, arr_t, next_station in sorted(graph[station], key=lambda x: x[0]):
if t > current_time:
return dfs(next_station, arr_t)
return float('-inf')

return [dfs(i, 0) for i in range(1, N)]

def main():
N, trains = read_input()
latest_arrival_times = find_latest_arrival_time(N, trains)
for time in latest_arrival_times:
if time == float('-inf'):
print('Unreachable')
else:
print(time)

if __name__ == '__main__':
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
doubao ```python
import collections

class Graph:
def __init__(self, n):
self.edges = collections.defaultdict(list)
self.n = n

def add_edge(self, u, v, w):
self.edges[u].append((v, w))

def dijkstra(self, src):
dist = [float('inf')] * self.n
dist[src] = 0
pq = [(0, src)]

while pq:
d, u = pq.pop(0)

if d > dist[u]:
continue

for v, w in self.edges[u]:
if dist[u] + w > dist[v]:
dist[v] = dist[u] + w
pq.append((dist[v], v))

return dist

N, M = map(int, input().split())
graph = Graph(N)

for _ in range(M):
l, d, k, c, a, b = map(int, input().split())
for i in range(k):
graph.add_edge(a - 1, b - 1, c)
a += d

distances = graph.dijkstra(0)

for i in range(1, N - 1):
if distances[i] == float('inf'):
print("Unreachable")
else:
print(distances[i])
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
import math
import heapq

sys.setrecursionlimit(1 << 25)
N, M = map(int, sys.stdin.readline().split())
N = int(N)
M = int(M)
from collections import defaultdict
import bisect

# Build reverse edges
adj = [[] for _ in range(N + 1)] # adj[s] = list of train patterns where B_i = s

for _ in range(M):
l_i, d_i, k_i, c_i, A_i, B_i = map(int, sys.stdin.readline().split())
adj[B_i].append((l_i, d_i, k_i, c_i, A_i))

import heapq

INF = 1 << 60 # Large enough number
f = [-INF] * (N + 1)
f[N] = INF # At destination N, we can arrive at any time

heap = [(-f[N], N)] # Max-heap by negative f[s] to get station with largest f[s]

while heap:
neg_fs, s = heapq.heappop(heap)
fs = -neg_fs
if f[s] < fs:
continue # Already updated to a larger f[s]
for pattern in adj[s]:
l_i, d_i, k_i, c_i, A_i = pattern

temp = f[s] - c_i - l_i
if temp < 0:
continue # No possible departure time from A_i via this train pattern
x_max = temp // d_i
x_max = min(x_max, k_i - 1)
if x_max < 0:
continue # No valid x_max
t_max = l_i + x_max * d_i
if t_max > f[A_i]:
f[A_i] = t_max
heapq.heappush(heap, (-f[A_i], A_i))

for S in range(1, N):
if f[S] == -INF:
print("Unreachable")
else:
print(int(f[S]))

if __name__ == '__main__':
threading.Thread(target=main).start()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
kimi ```python
import sys
input = sys.stdin.readline
INF = 10 ** 18
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
(l, d, k, c, A, B) = map(int, input().split())
graph[A - 1].append((l + (k - 1) * d, c, B - 1))
for i in range(N):
if not graph[i]:
graph[i].append((INF, 0, i))
dp = [-1] * N
dp[-1] = 0
import heapq
q = [(0, N - 1)]
while q:
(t, s) = heapq.heappop(q)
if dp[s] != -1:
continue
dp[s] = t
for (nt, c, ns) in graph[s]:
if nt + c <= t:
continue
if dp[ns] == -1 or dp[ns] < nt + c:
heapq.heappush(q, (nt + c, ns))
for i in range(N - 1):
if dp[i] == -1:
print('Unreachable')
else:
print(dp[i])
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
minimax ```python
import heapq

def f(S, N, trains):
# Create a graph where each station is a node and each train is an edge
graph = [[] for _ in range(N)]
for l, d, k, c, A, B in trains:
for t in range(l, l + k * d, d):
heapq.heappush(graph[A - 1], (t + c, B - 1))

# Perform Dijkstra's algorithm to find the latest arrival time at station N from station S
# Initialize distances with -infinity
distances = [-float('inf')] * N
distances[S - 1] = 0
heap = [(0, S - 1)] # (time, station)

while heap:
current_time, current_station = heapq.heappop(heap)
if current_time < distances[current_station]:
continue
for next_time, next_station in graph[current_station]:
if next_time > current_time:
# Relaxation step: update the distance if a later arrival time is found
if distances[next_station] < next_time:
distances[next_station] = next_time
heapq.heappush(heap, (next		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
wenxinyiyan ```python
from collections import defaultdict
import heapq
import sys

# Define a class for train events
class TrainEvent:
def __init__(self, time, station, is_departure):
self.time = time
self.station = station
self.is_departure = is_departure

def __lt__(self, other):
if self.time != other.time:
return self.time < other.time
return self.is_departure < other.is_departure

# Read input
N, M = map(int, input().split())
trains = defaultdict(list)
for _ in range(M):
l, d, k, c, A, B = map(int, input().split())
for t in range(l, l + d * k, d):
trains[(A, t)].append((B, t + c))

# Initialize data structures
events = []
f = [-float('inf')] * N
f[N - 1] = float('inf') # Destination station has infinite arrival time
visited = set()

# Add initial events (departures from station 1)
for B, arrival_time in trains[(1, 0)]:
heapq.heappush(events, TrainEvent(arrival_time, B, False))

# Process events
while events:
event = heapq.heappop(events)
if event.is_departure:
# Check if we can improve the arrival time at the station
if f[event.station - 1] < event.time:
f[event.station - 1] = event.time
# Add all possible departures from this station
for next_station, next_arrival_time in trains[(event.station, event.time)]:
if (event.station, next_station, next_arrival_time) not in visited:
visited.add((event.station, next_station, next_arrival_time))
heapq.heappush(events, TrainEvent(next_arrival_time, next_station, False))
else:
# Add possible departure from this station if it's not visited before
for next_departure_time, next_station in trains[(event.station, event.time)]:
if (event.station, next_station, next_departure_time) not in visited:
visited.add((event.station, next_station, next_departure_time))
heapq.heappush(events, TrainEvent(next_departure_time, event.station, True))

# Print results
for i in range(N - 1):
if f[i] == -float('inf'):
print('Unreachable')
else:
print(f[i])
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
zhipu ```python
import sys
import heapq

def main():
input = sys.stdin.read
data = input().split()

index = 0
N = int(data[index])
index += 1
M = int(data[index])
index += 1

trains = []
for _ in range(M):
l = int(data[index])
index += 1
d = int(data[index])
index += 1
k = int(data[index])
index += 1
c = int(data[index])
index += 1
A = int(data[index]) - 1
index += 1
B = int(data[index]) - 1
index += 1
trains.append((l, d, k, c, A, B))

# Graph adjacency list
graph = [[] for _ in range(N)]

for l, d, k, c, A, B in trains:
for i in range(k):
departure_time = l + i * d
arrival_time = departure_time + c
graph[A].append((departure_time, arrival_time, B))

# Function to perform Dijkstra's algorithm from a given start node
def dijkstra(start):
# Priority queue: (arrival_time, node)
pq = []
# Distance to each node, initialized to -inf (unreachable)
dist = [-float('inf')] * N
dist[start] = float('inf')

heapq.heappush(pq, (-dist[start], start))

while pq:
current_dist, u = heapq.heappop(pq)
current_dist = -current_dist

if current_dist < dist[u]:
continue

for departure_time, arrival_time, v in graph[u]:
if arrival_time <= dist[u] and arrival_time > dist[v]:
dist[v] = arrival_time
heapq.heappush(pq, (-dist[v], v))

return dist

# Calculate the latest arrival times from station N-1 to all other stations
latest_arrival_times = dijkstra(N-1)

# Output the results for stations 1 to N-2
for i in range(N-1):
if latest_arrival_times[i] == -float('inf'):
print('Unreachable')
else:
print(latest_arrival_times[i])

if __name__ == "__main__":
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]
deepseek-v3 ```python
import sys
import heapq

def main():
N, M = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
l, d, k, c, A, B = map(int, sys.stdin.readline().split())
adj[B].append((A, l, d, k, c)) # Reverse the edges for Dijkstra

# Initialize distances
dist = [ -1 ] * (N+1)
dist[N] = float('inf')
pq = []
heapq.heappush(pq, (-dist[N], N))

while pq:
current_dist, u = heapq.heappop(pq)
current_dist = -current_dist
if current_dist < dist[u]:
continue
for v, l, d, k, c in adj[u]:
# Compute the latest departure time from v to u
# The latest departure time from v is min(l + (k-1)*d, current_dist - c)
max_depart = min(l + (k-1) * d, current_dist - c)
if max_depart < l:
continue
# The latest arrival time at v is max_depart
if max_depart > dist[v]:
dist[v] = max_depart
heapq.heappush(pq, (-dist[v], v))

for i in range(1, N):
if dist[i] == -1:
print("Unreachable")
else:
print(dist[i])

if __name__ == "__main__":
main()
```		 [{"input": "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\n", "output": "55\n56\n58\n60\n17\n", "testtype": "stdin"}, {"input": "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\n", "output": "1000000000000000000\nUnreachable\n1\nUnreachable\n", "testtype": "stdin"}, {"input": "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\n", "output": "720358\n77158\n540926\n255168\n969295\nUnreachable\n369586\n466218\n343148\n541289\n42739\n165772\n618082\n16582\n591828\n", "testtype": "stdin"}]