Harryxun/stf_run huggingface dataset:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=np.int)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n, dtype=np.int)
    while k:
        if k % 2:
            answer = answer @ can
        can = can @ can
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = [[int(c) for c in input().split()] for _ in range(n)]
    can = np.matrix(can, 'O')
    
    # for i in range(n):
    #     for j, e in enumerate(int(c) for c in input().split()):
    #         can[i, j] = e

    b = np.eye(n, n, 0, 'O')
    while k:
        b = [b, b*can % MOD][k & 1]
        can = can*can % MOD
        k >>= 1

    print(b.sum() % MOD)

    # answer = np.eye(n, dtype=int)
    # while k:
    #     if k % 2:
    #         answer = np.dot(answer, can) % MOD
    #     can = np.dot(can, can) % MOD
    #     k //= 2

    # total = 0
    # for i in range(n):
    #     for j in range(n):
    #         total += answer[i,j]
    #         if total >= MOD:
    #             total -= MOD

    # print(total)


if __name__ == "__main__":
    main()
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
for i in range(N):
    a = A.pop(0)
    B.append(0)
    B.append(0)
ans = 0
B.pop()
for i in range(N-1):
    a = B.pop()
    ans += b
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
k = N - 2
a = A.pop()
ans = a
n = k // 2
for i in range(n):
    a = A.pop()
    ans += 2*a
if k - 2*n == 1:
    ans += A[-1]

print(ans)
N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
B = list(range(N))
def Temp(x):
  Temp = T-0.006*x
  return(Temp)
for i in range(N):
  B[i] = abs(Temp(H[i])-A)
ans = min(B)
print(B.index(ans)+1)

### FIXED CODE ###

X,Y = map(int,input().split())
ans = X+Y//2
print(ans)
n = int(input(),10)
sort_list = list()

for i in range(0,n):
    sort_list.append(int(input(),10))

for i in range(1,n):
    
    for j in range(0,n):
        print(sort_list[j])
        if j is not n - 1:
            print(" ")
        else:
            print("\n")
    
    tmp = sort_list[i]
    int j = i - 1
    while j >= 0 and sort_list[i] > v:
        sort_list[j+1] = sort_list[j]
        j--
    sort_list[j+1] = v




### FIXED CODE ###

import sys

n = input()
sort_list = list()

sort_list = map(int, raw_input().split())

for i in range(0,n):
    
    
    tmp = sort_list[i]
    j = i - 1
    while j >= 0 and sort_list[j] > tmp:
        sort_list[j+1] = sort_list[j]
        j = j - 1

    sort_list[j+1] = tmp


    for k in range(0,n):
        sys.stdout.write(str(sort_list[k]))
        if k is not n - 1:
            sys.stdout.write(" ")
        elif i is not n - 1:
            sys.stdout.write("\n")
            
print("")
N, K = map(int, input().split())
A_i = list(map(int, input().split()))

place = 1
road = []
cycle = 0
begin = 0

while K != 0:
    road.append(place)
    place = A_i[place - 1]
    K -= 1

    if place in road:
        cycle = len(road) - road.index(place)
        begin = road.index(place)
        break

K = begin + (K - begin) % cycle

while K !=0:
    place = A_i[place - 1]
    K -= 1

print(place)


### FIXED CODE ###

N, K = map(int, input().split())
A_i = list(map(int, input().split()))

place = 1
road = [0 for i in range(N)]
cycle = 0

road[0] = 1

while K != 0:
    place = A_i[place - 1]
    K -= 1
    if road[place - 1] == 1:
        loop_place = place
        break
    road[place - 1] = 1

while K != 0:
    loop_place = A_i[loop_place - 1]
    cycle += 1

    if place == loop_place:
        break

if cycle != 0:
    K = K % cycle

while K != 0:
    place = A_i[place - 1]
    K -= 1

print(place)
N = int(input())
num_list = list(map(int, input().split()))
 
a=0
for i in num_list:
  if i%2==0 and (i%3!=0 and i%5!=0):
  	print('DENIED')
    exit()

print('APPROVED')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

for i in A:
  if i%2 == 0 and i%3 != 0 and i%5 != 0:
    print('DENIED')
    exit()
print('APPROVED')
N = int(input())
A = list(map(int, input().split()))

import math
from itertools import permutations

lis = [0]*N
for i in range(N):
    lis[i] = i

num = math.factorial(N)

scores = [0]*num
i = 0
for v in permutations(lis, N):
    score = 0
    for j in range(N):
        score += abs(v.index(j)-j) * A[j]
    scores[i] = score
    i += 1

print(max(scores))

### FIXED CODE ###

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)
s = input()
t = input()
ls = len(s)
lt = len(t)
S = s*(lt//ls+2)
N = len(S)
mod = 2**61-1
base = 4#ランダムに撮るのが好ましい
power = [1]*N#power[i] = base^iの配列
for i in range(1, N):
    power[i] = power[i-1]*base%mod
rolling_hash = [0]*(N+1)
k = lt
for i, s in enumerate(S[:k]):
    rolling_hash[i+1] = rolling_hash[i]*base+ord(s)
for i in range(k, N):
    rolling_hash[i+1] = ((rolling_hash[i]-ord(S[i-k])*power[k-1])*base+ord(S[i]))%mod
thash = sum(ord(t[i])*power[lt-i-1] for i in range(lt))
is_same = [False]*ls
for i, h in enumerate(rolling_hash[k:ls+k]):
    if h == thash:
        is_same[i] = True
length = [-1]*N
is_visited = [False]*N
def rec(i):
    if length[i]>=0:
        return length[i]
    if is_visited[i]:
        return -1
    is_visited[i] = True
    if not is_same[i]:
        length[i] = 0
        return 0
    ni = (i+lt)%ls
    length[i] = rec(ni)+1
    if length[i] == 0:
        return -1
    return length[i]
for i in range(ls):
    if is_visited[i]:
        continue
    res = rec(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)
print(ans)


### FIXED CODE ###


def search_rolling_hash(S, T):
    base = 1234
    mod = 10**9+7
    n, m = len(S), len(T)
    rolling_hash = [0]*(n-m+1)  
    rolling_hash[0] = ord(S[0])
    b_m = pow(base, m, mod)
    T_hash = ord(T[0])
    start_index = []
    for i in range(1, m):
        rolling_hash[0]*=base
        rolling_hash[0]+=ord(S[i])
        rolling_hash[0]%=mod
        T_hash = (T_hash*base+ord(T[i]))%mod
    if rolling_hash[0] == T_hash: start_index.append(0)
    for i in range(1, ls):
        rolling_hash[i] = (rolling_hash[i-1]*base-ord(S[i-1])*b_m+ord(S[i+m-1]))%mod
        if rolling_hash[i] == T_hash: start_index.append(i)
    return start_index
import sys
s = input()
t = input()
ls, lt = len(s), len(t)
S = s*(lt//ls+2)
index = search_rolling_hash(S, t)
flag = [False]*ls
for i in index:
    flag[i] = True
stack = []
inf = float('inf')
cnt = [inf]*ls
for i in range(ls):
    if flag[i] == False:
        stack.append(i)
        cnt[i] = 0
while stack:
    x = stack.pop()
    y = (x-lt)%ls
    if cnt[y] == inf:
        cnt[y] = cnt[x]+1
        stack.append(y)
ans = max(cnt)
if ans == inf:
    print(-1)
else:
    print(ans)
n = int(input())
li = list(map(int, input().split()))

ans_list = []
a = 0
b = 0
for c, l in enumerate(li):
  if l <= a:
    b += 1
    if c == n - 1:
      ans_list.append(b)
  else:
    if c != 0:
      ans_list.append(b)
    b = 0
  a = l

ans = max(ans_list)
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))

ans_list = []
a = 0
b = 0
for c, l in enumerate(li):
  if l <= a:
    b += 1
    if c == n - 1:
      ans_list.append(b)
  else:
    if c != 0:
      ans_list.append(b)
    b = 0
  a = l

if len(ans_list) != 0:
  ans = max(ans_list)
else:
  ans = 0
print(ans)
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    S.append(s)
L=[[] for _ in range(H)]
R=[[] for _ in range(H)]
D=[[] for _ in range(H)]
U=[[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            L[i].append(0)
        if S[i][W-1-j]=="#":
            R[i].append(0)
        else:
            if j==0:
                L[i].append(1)
                R[i].append(1)
            else:
                L[i].append(L[i][j-1]+1)
                R[i].append(R[i][j-1]+1)

for i in range(W):
    for j in range(H):
        if S[j][i]=="#":
            U[j].append(0)
        if S[H-1-j][i]=="#":
            D[j].append(0)
        else:
            if j==0:
                U[j].append(1)
                D[j].append(1)
            else:
                U[j].append(U[j-1][i]+1)
                D[j].append(D[j-1][i]+1)
ans=0

for i in range(H):
    for j in range(W):
        tmp=L[i][j]+R[i][W-1-j]+U[i][j]+D[H-1-i][j]-3
        ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    S.append(s)
L=[[0]*W for _ in range(H)]
R=[[0]*W for _ in range(H)]
D=[[0]*W for _ in range(H)]
U=[[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            if j==0:
                L[i][j]=1
            else:
                L[i][j]=L[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):
        if S[i][j]==".":
            if j==(W-1):
                R[i][j]=1
            else:
                R[i][j]=R[i][j+1]+1

for j in range(W):
    for i in range(H-1,-1,-1):
        if S[i][j]==".":
            if i==(H-1):
                D[i][j]=1
            else:
                D[i][j]=D[i+1][j]+1

for j in range(W):
    for i in range(H):
        if S[i][j]==".":
            if i==0:
                U[i][j]=1
            else:
                U[i][j]=U[i-1][j]+1
ans=0
X=[[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j]=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    ans=max(ans,max(X[i]))
print(ans)
64145 123 456

### FIXED CODE ###

x, y, z = map(int, input().split())

x -= z
y += z
print(x // y)
def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = {}
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a in d1:
      d1[a].append(b)
    else:
      d1[a] = [b]
  result = 0
  d2 = {}
  maxb = -1
  maxbn = -1
  for i in _range(1, m + 1):
    if i in d1:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 0
        d2[j] += 1
        if j > maxb:
          maxbn = maxb
          maxb = j
        elif j > maxbn:
          maxbn = j
    else:
      if _len(d2) == 0:
        continue
    result += maxb
    if d2[maxb] == 1:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
        maxbn = -1
      else:
        if maxbn != -1:
          maxb = maxbn
          maxbn = -1
        else:
          maxb = _max(d2.keys())
    else:
      d2[maxb] -= 1
  print(result)
main()

### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
n=int(input())
l=[int(i) for i in input().split()]

l.sort()

def func(one,two,three):
  if len(set([one,two,three]))==3 and one+two>three:
    return True
  return False

ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      one=l[i]
      two=l[j]
      three0l[k]
      if func(one,two,three):
        ans+=1
        
print(ans)
      

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
 
l.sort()
 
def func(one,two,three):
  if len({one,two,three})==3 and one+two>three:
    return True
  return False
 
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      one=l[i]
      two=l[j]
      three=l[k]
      if func(one,two,three):
        ans+=1
        
print(ans)
k = int(input())
x = int(input())

print(*list(range(x-k+1, x)) + list(range(x, x+k)))

### FIXED CODE ###

k, x = map(int, input().split())

print(*list(range(x-k+1, x)) + list(range(x, x+k)))
X,N = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

if N != 0:
    if X in p:
        sorted_p = sorted(p)

        for x in range(N-1):
            diff = abs(X - sorted_p[x])
            if diff < abs(X-sorted_p[x+1]):
                break
            elif x == N-2 and diff > abs(X-sorted_p[x+1]):
                x = N-1
        
            
        def checknum(d,loweridx,upperidx):
            upper = sorted_p[upperidx]
            lower = sorted_p[loweridx]
            if X-d == lower:
                if X+d == upper:
                    if loweridx == 0:
                        print(X-d-1)
                    elif upperidx == N-1:
                        print(X+d+1)
                    else:
                        checknum(d+1,loweridx-1,upperidx+1)
                elif X-d == lower and X+d != upper:
                    print(X+d)        
            else:
                return print(X-d)

        if x == 0:
            print(X-1)
        elif x == N-1:
            a=1
            while(sorted_p[x-a] == X):
                a += 1
            if sorted_p[x-a] != X-1:
                print(X-1)
            else:
                print(X+1)
        else:
            checknum(1,x-1,x+1)
    else:
        print(X)
else:
    print(X)

### FIXED CODE ###

X,N = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

for d in range(X+1):
    for f in [-1,1]:
        a = X + d*f
        if p.count(a) == 0:
            print(a)
            exit()
from collections import deque
from bisect import bisect_right

n = int(input())
alst = list(map(int, input().split()))
alst.sort()
pos = 0
ans = 0
while 1:
    num = alst[pos]
    try:
        if num != alst[pos + 1]:
            ans += 1
    except IndexError:
        print(ans)
        break
    judge_pos = bisect_right(alst, num * 2)
    while 1:
        try:
            if alst[judge_pos] % num != 0:
                judge_pos += 1
            else:
                alst.pop(judge_pos)
        except  IndexError:
            break
    pos += 1

### FIXED CODE ###

n = int(input())
alst = list(map(int, input().split()))
alst.sort()
tmp = [0 for _ in range(10 ** 6 + 10)]
ans = 0
flg = True
if n == 1:
    print(1)
    exit()
if alst[0] == 1:
    if alst[1] == 1:
        print(0)
    else:
        print(1)
    exit()
for num in alst:
    if tmp[num] == 2:
        if flg:
            ans -= 1
            flg = False
        continue
    flg = True
    if tmp[num] == 1:
        continue
    ans += 1
    tmp[num] = 2
    xx = num * 2
    while xx < 10 **  6 + 1:
        tmp[xx] = 1
        xx += num
print(ans)
r = int(input())
if n < 1200:
    print("ABC")
elif n < 2800:
    print("AEC")
else:
    print("AGC")

### FIXED CODE ###

n = int(input())
if n < 1200:
    print("ABC")
elif n < 2800:
    print("ARC")
else:
    print("AGC")
import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if m[x2][y2] == '@':
                    break
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

                # if (0 <= x2 < H) and (0 <= y2 < W):
                #     if m[x2][y2] == '@':
                #         break
                #     elif M[x2][y2] == -1:
                #         M[x2][y2] = d + 1
                #         q.append((d + 1, x2, y2))
                #     elif M[x2][y2] == d + 1:
                #         continue
                #     else:
                #         break
                # else:
                #     break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
n = input()
p = input().split()


n = int(n)

cnt=0

for i in range(1,n-1):
  if(p[i]<p[i+1] and p[i]>p[i-1]) or (p[i]>p[i+1] and p[i]<p[i-1]):
    cnt+=1;

  
print(cnt)

### FIXED CODE ###

s=[]
s = input()
cnt=0
 
if(s[0] == s[1]):
    cnt+=1

if(s[0] == s[2]):
    cnt+=1
 
 
if(s[0] == s[3]):
    cnt+=1
 
 
if(s[1] == s[2]):
    cnt+=1
 
 
if(s[1] == s[3]):
    cnt+=1
 
 
if(s[2] == s[3]):
    cnt+=1
 
 
if cnt == 2 :
  print("Yes")
else :
  print("No")
s,t=map(str,input().spilt())
a,b=map(int,input().split())
u=input()
if u==s:
  print(s-1,t)
else:
  print(s,t-1)

### FIXED CODE ###

s, t = map(str, input().split())
a, b = map(int,input().split())
u = input()

if u==s:
    print(a-1, b)

else:
    print(a, b-1)
# 2020/05/02
# AtCoder Beginner Contest 165 - C

a = list()
def mkArray(in_list, sav_val, cnt):
    if cnt >= m:
        a.append(in_list)
        return 0
    else:
        for x in range(sav_val, m + 1):
            wk_list = list()
            wk_list.extend(in_list)
            wk_list.append(x)
            mkArray(wk_list, x, cnt + 1)

# Input
n, m, q = map(int,input().split())
abcd = list()

for i in range(q):
    w_abcd = list(map(int,input().split()))
    abcd.append(w_abcd)

# Make Array
w_a = list()
mkArray(w_a, 1, 0)

# Search
ans = 0
for i in range(len(a)):
    wans = 0
    for j in range(q):
        if a[i][abcd[j][1]-1] - a[i][abcd[j][0]-1] == abcd[j][2]:
            wans = wans + abcd[j][3]

    if wans > ans:
        ans = wans

# Output
print(ans)


### FIXED CODE ###

# 2020/05/02
# AtCoder Beginner Contest 165 - C

a = list()
def mkArray(in_list, sav_val, cnt):
    if cnt >= n:
        a.append(in_list)
        return 0
    else:
        for x in range(sav_val, m + 1):
            wk_list = list()
            wk_list.extend(in_list)
            wk_list.append(x)
            mkArray(wk_list, x, cnt + 1)

# Input
n, m, q = map(int,input().split())
abcd = list()

for i in range(q):
    w_abcd = list(map(int,input().split()))
    abcd.append(w_abcd)

# Make Array
w_a = list()
mkArray(w_a, 1, 0)

# Search
ans = 0
for i in range(len(a)):
    wans = 0
    for j in range(q):
        if a[i][abcd[j][1]-1] - a[i][abcd[j][0]-1] == abcd[j][2]:
            wans = wans + abcd[j][3]

    if wans > ans:
        ans = wans

# Output
print(ans)
import math
import numpy as np
n, x0 = map(int, input().split())
x = np.array(list(map(int, input().split()))) - x0
xx = x[0]
for i in range(1, n):
    xx = math.gcd(xx, x[i])
print(xx)

### FIXED CODE ###

from fractions import gcd
import numpy as np
n, x0 = map(int, input().split())
x = np.abs(np.array(list(map(int, input().split()))) - x0)
xx = x[0]
for i in range(1, n):
    xx = gcd(xx, x[i])
print(xx)
count = 0

while True:  
 
  x = raw_input()
  
   count += 1
   
    if x == '0':
      break
    
  print('Case' + str(count) + ': ' + x)

### FIXED CODE ###

count = 0

while True:  
 
  x = raw_input()
  
  count += 1
   
  if x == '0':
    break
    
  print('Case ' + str(count) + ': ' + x)
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))
finished=0

while(not finished==v):
    now=q.get()
#    print("get",now)
    nowv=now[1]
    finished+=1
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
            
#            print("put",(dis[vt],vt))

    
for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

### FIXED CODE ###

'''
????????£????????????1??????????????????
??\???C++??§????????????????§£?±???????????????????????????????????????§???
??????python??§??????????????????Accept??§??????????????????
????????£??¨optimization??????????????§??????
??§????????????Wrong Answer??§?????????
???????????????????????????????????????????????????
Online Judge???????????????Public Solutions??§
????????????nanae?????????python3????????????????????????
????????£??¨?????????????????????
???????????????????????????0.06?§????????????§??????
'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))


while(not q.empty()):
    now=q.get()
    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''

finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       '''

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])
i=0
while True:
    i+=1
    x=raw_input()
    if x==0:
        break
    print 'Case %d: %d' % (i,x)

### FIXED CODE ###

i=0
while True:
    i+=1
    x=raw_input()
    if x=='0':
        break
    print 'Case %d: %s' % (i,x)