Harryxun/stf_run huggingface dataset:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    ans = -INF
    for i in range(N):
        # iを含むサイクルの探索
        cycle = []
        c = i
        while True:
            c = P[c]
            cycle.append(c)
            if c == i:
                break
        len_cycle = len(cycle)

        # 最大スコアの探索
        score = 0

        # Kの残り
        r = K
        cycle_score_total = sum([C[j] for j in cycle])
        if len_cycle < K:
            # 周回して増えるなら周回する
            if cycle_score_total > 0:
                score += K // len_cycle * cycle_score_total
                # 周回後の余り
                r = K % len_cycle
            # 周回して増えないなら周回しない
            else:
                # サイクル一周までの範囲でどこまでもいける
                r = len_cycle

        # Kの残っている範囲で最大スコア探索
        cycle_score = [C[cycle[j]] for j in range(r)]
        cycle_score_cum = list(itertools.accumulate(cycle_score))
        score += max(cycle_score_cum)

        ans = max(score, ans)

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()
    P = LI_()
    C = LI()

    ans = -INF
    for i in range(N):
        # iを含むサイクルの探索
        cycle = []
        c = i
        while True:
            c = P[c]
            cycle.append(c)
            if c == i:
                break
        len_cycle = len(cycle)
        # print(i, cycle, [C[j] for j in cycle])

        # 最大スコアの探索
        score = 0
        cycle_score_total = sum([C[j] for j in cycle])
        cycle_score_cum = list(itertools.accumulate([C[j] for j in cycle]))
        # 終了地点をjと決める
        for j in range(min(len_cycle, K)):
            score = cycle_score_cum[j]
            if cycle_score_total > 0:
                score += (K - j - 1) // len_cycle * cycle_score_total
            # print(j, score)
            ans = max(score, ans)

    print(ans)

if __name__ == '__main__':
    resolve()
shio = string(input())
x = 0
for i in shio:
  if shio = "0":
    x+=1


### FIXED CODE ###

shio = str(raw_input())
counter = 0
i=0
while i < 3:
  if shio[i] == "1":
    counter +=1
  i +=1
print(counter)
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

def solve(s):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[0][0] = 0
    
    if s[0] == W or s[1] == H or S[1][0] == "#":
        return visited

    visited[s[1]][s[0]] = 1
    
    q = deque()
    q.append(s)

    while q:
        x, y = q.popleft()

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans_1 = (0, 0, 0)
for y, v in enumerate(solve((0, 1))):
    for x, c in enumerate(v):
        if c >= ans_1[2]:
            ans_1 = (x, y, c)
        
ans_2 = (0, 0, 0)
for y, v in enumerate(solve((1, 0))):
    for x, c in enumerate(v):
        if c >= ans_2[2]:
            ans_2 = (x, y, c)
        
if ans_1[0] == ans_2[0] and ans_1[1] == ans_2[1]:
    print(min(ans_1[2], ans_2[2]))
else:
    print(ans_1[2] + ans_2[2])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

def solve(x, y):
    offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[-1] * W for _ in range(H)]
    visited[y][x] = 0
    
    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()

        for u, v in offset:
            if not (0 <= x + u < W) or not (0 <= y + v < H):
                continue

            if visited[y + v][x + u] > -1 or S[y + v][x + u] == "#":
                continue

            visited[y + v][x + u] = visited[y][x] + 1
            q.append((x + u, y + v))
            
    return visited

ans = 0
for y, ss in enumerate(S):
    for x, s in enumerate(ss):
        if s == ".":
            ans = max(ans, max(max(v) for v in solve(x, y)))

print(ans)
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1
    g = [-1] * (n+1)
    g[0] = 0
    for i in range(1, n+1):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def popcount(x):
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    return x & 0x0000007f

def solve():
    n = ni()
    X = list(map(int, list(ns())))
    p = sum(X)
    pl, ps = p+1, p-1

    g = [-1] * (n+5)
    g[0] = 0
    for i in range(1, n+5):
        g[i] = g[i % popcount(i)] + 1
    ql = qs = 0
    for x in X:
        ql = (ql * 2 + x) % pl
        if ps > 0:
            qs = (qs * 2 + x) % ps
    vl = vs = 1
    ans = [0]*n
    for i in range(n-1, -1, -1):
        if X[i]:
            if ps > 0:
                ans[i] = g[(qs-vs)%ps] + 1
        else:
            ans[i] = g[(ql+vl)%pl] + 1
        if ps > 0:
            vs = vs * 2 % ps
        vl = vl * 2 % pl
    prn(ans)
    return

solve()
import sys

a,b = map(int, sys.stdin.readline().rstrip().split(' '))
print("{} {}".format(a*b, (a+b)*2)

### FIXED CODE ###

import sys

a,b = map(int, sys.stdin.readline().rstrip().split(' '))
print("{} {}".format(a*b,(a+b)*2))
import fractions
from functools import reduce
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
a2 = a.copy()
res = []
for i in range(0,n):
    a2.pop(i)
    res.append(reduce(fractions.gcd,a2))
    a2 = a.copy()
print(max(res))

### FIXED CODE ###

a,b,t=map(int,input().split());print(int(t/a)*b)
n = int(input)
for i in range(n):
    std_in = input.split()
    dat.append([std_in[0], int(std_in[1])])

for i, e in enumerate(dat, start=1):
    e[1] = -e[1]  # 点数を降順ソートするために点数をマイナスにする。
    e.append(i)  # ソート前の順序

    sorted_list = sorted(dat)  # 都市名と点数のマイナス値で昇順ソート

for i, s in enumerate(sorted_list):
    # 順序を出力
    print(sorted_list[i][2])


### FIXED CODE ###

n = int(input())
dat = []
for i in range(n):
    std_in = input().split()
    dat.append([std_in[0], int(std_in[1])])
     
for i, e in enumerate(dat, start=1):
    e[1] = -e[1]  # 点数を降順ソートするために点数をマイナスにする。
    e.append(i)  # ソート前の順序
     
sorted_list = sorted(dat)  # 都市名と点数のマイナス値で昇順ソート
     
for i, s in enumerate(sorted_list):
    # 順序を出力
    print(sorted_list[i][2])
s=input_raw()
print(s)

### FIXED CODE ###

s=input()

data = s.split('/')
out = '2018/01/'+data[2]

print(out)
a = int(input)
s = input()

if(a>=3200):
    print(s)
else:
    print("red")

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)
else:
    print("red")
S=int(input())
T = input().split()
U = [int(T(i)) for i in S]
U.sort
r = 0

for i in S-1:
  if(T[i] == T[i+1]):
    r++
    
if(r==0):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S=int(input())
T = input().split()
U = [int(i) for i in T]
U.sort()
r = 0

for i in range(S-1):
  if(U[i] == U[i+1]):
    r+=1
    
if(r==0):
  print("YES")
else:
  print("NO")
import math
num = int(input())
words = {}

for i in range(num):
  a = str(sorted(list(input())))
  
  if a in words:
    words[a] += 1
  else:
  	words[a] = 1

points = list(words.values())
sum = 0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(len(points)):
  sum += combinations_count(points[i], 2)
print(sum)

### FIXED CODE ###

import math
num = int(input())
words = {}

for i in range(num):
  a = str(sorted(list(input())))
  
  if a in words:
    words[a] += 1
  else:
  	words[a] = 1

points = list(words.values())
sum = 0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(len(points)):
  if points[i] > 1:
  	sum += combinations_count(points[i], 2)
print(sum)
import sys
import collections
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")

n=int(input())
d=list(map(int,input().split()))
d.append(0)
c=collections.Counter(d)
if c.most_common()[0][1]>2:
    print(0)
    quit()
if 0 in c:
    if c[0]==2:
        print(0)
        quit()
if 12 in c:
    if c[12]==2:
        print(0)
        quit()
li=list(map(int,c.keys()))

ans=0
for i in range(2**len(li)):
    hour=[]
    for j in range(len(li)):
        if c[li[j]]==2:
            hour.append(li[j])
            hour.append(24-li[j])
            break
        if i^(1<<j):
            hour.append(li[j])
        else:
            hour.append(24-li[j])
    hour.sort()

    tmp=24+hour[0]-hour[-1]
    for j in range(len(li)-1):
        tmp=min(tmp,hour[j+1]-hour[j])
    ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

import sys
import collections
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")

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

c=collections.Counter(d)
if c.most_common()[0][1]>2:
    print(0)
    quit()
if 0 in c:
    if c[0]==1:
        print(0)
        quit()

li=list(map(int,c.keys()))
li.append(0)
ans=0
# print(li)
# print(len(li))
for i in range(2**len(li)):
    hour=[]
    for j in range(len(li)):
        if c[li[j]]==2:
            hour.append(li[j])
            hour.append(24-li[j])
            continue
        if i&(1<<j):
            hour.append(li[j])
        else:
            hour.append(24-li[j])
    hour.sort()
    # print(hour)
    tmp=24+hour[0]-hour[-1]
    for j in range(len(hour)-1):
        tmp=min(tmp,hour[j+1]-hour[j])
    # print(tmp)
    ans=max(ans,tmp)
print(ans)
def resolve():
    '''
    code here
    '''
    N = int(input())
    As = [int(item) for item in input().split()]

    deff_list = [0]
    for i in range(1,N):
        deff_list.append(As[i] - As[i-1])

    res_list = []
    is_first = True
    any_plus = False
    for i in range(1,N):
        if deff_list[i] > 0:
            any_plus = True
        
        if is_first and any_plus and deff_list[i] < 0 :
            res_list.append([i-1, As[i-1]])
            is_first = False

        if deff_list[i-1] > 0 and deff_list[i] < 0:
            res_list.append([i-1, As[i-1]])
        


    else:
        if deff_list[N-1] >= 0 and any_plus:
            res_list.append([N-1, As[N-1]])

    prev = 0
    res = 1000
    for i, val in res_list:
        temp_min = min(As[prev:i])
        temp_num = res //  temp_min
        res = temp_num * val + res % temp_min
        prev = i

    print(res)



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    N = int(input())
    As = [int(item) for item in input().split()]

    deff_list = [0]
    for i in range(1,N):
        deff_list.append(As[i] - As[i-1])

    prev = 1000
    res = 1000
    for i in range(1, N):
        if deff_list[i] >= 0:
            res = (prev // As[i-1]) * As[i] + prev % As[i-1]
        
        prev = res
    
    print(res)



if __name__ == "__main__":
    resolve()
n = int(input())

if x >= 30:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

x = int(input())
 
if x >= 30:
  print('Yes')
else:
  print('No')
a = input()
if a = "Sunny":
  print("Cloudy")
elif a = "Cloudy":
  print("Rainy")
else:
  print("Sunny")
  

### FIXED CODE ###

a = input()
if a=='Sunny':
  print('Cloudy')
elif a=='Cloudy':
  print('Rainy')
elif a=='Rainy':
  print('Sunny')
for i in range(0,n-2):
    if s[i] == 'A':
        if s[i+1] == 'B':
            if s[i+2] == 'C':
                c += 1
        
print(c)

### FIXED CODE ###

n = int(input())
s = input()

c = 0

for i in range(0,n-2):
    if s[i] == 'A':
        if s[i+1] == 'B':
            if s[i+2] == 'C':
                c += 1
        
print(c)
D = list(map(int,input().split()))

if D[2] > D[0] + D[1]:
  print(No)
else:
  print(Yes)

### FIXED CODE ###

D = list(map(int,input().split()))

if D[2] > D[0] + D[1]:
  print("No")
else:
  print("Yes")
import numpy as np
import math

N = int(input())
A = np.array([int(i) for i in (input()).split(" ")])
minA = np.min(A)

if(minA == np.max(A)):
    print(minA)
else:
    check = np.unique(minA // np.arange(1,minA))
    #check = minA // np.arange(1,minA)
    for i in check[::-1]:
        #全てのAに対してiで割り切れるか＝最大公約数
        #iで割り切れた数＝len(A)-1なら，残りの数にiをかけて最大公約数に出来る．
        num = np.sum((A % i>0))
        if(num < 2):
            j = A[np.where(A % i>0)][0]
            #print(i,j,i*j//math.gcd(i,j))
            if(i*j//math.gcd(i,j) < 10**9):
                print(i)
                break

### FIXED CODE ###

a,b,t = map(int, (input()).split(" "))
n = t//a
print("{}".format(n*b,'d'))
N=int(input())
A=list(map(),int.input().split())
count=0
for i in range(N):
  if A[i]%2==1:
    count+=1

ans=["YES","NO"]

print(ans[count%2])
    
    
    
    

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
for i in range(N):
  if A[i]%2==1:
    count+=1

ans=["YES","NO"]

print(ans[count%2])
n = int(input())
record = [ [ [ [0 for r in range(10)] for f in range(3)] ] for b in range(4)]
for i in range(n):
    b,f,r,v = [int(a) in input().split(" ")]
    record[b - 1][f - 1][r - 1] += v
for b in range(4):
    for f in record[b]):
        print( " ".join([str(x) for x in f])
   if b != 3:
        print("#" * 20)
        

### FIXED CODE ###

n = int(input())
record = [ [ [0 for r in range(10)] for f in range(3)] for b in range(4)]
for _ in range(n):
    b,f,r,v = [int(i) for i in input().split(" ")]
    record[b - 1][f - 1][r - 1] += v
for b1 in range(4):
    for f in record[b1]:
        print(" "+" ".join([str(x) for x in f]))
    if b1 != 3:
        print("#" * 20)
import re, sys
print sum(map(int,re.sub("\w+|\s+"," ",sys.stdin.readlines()).strip().split()))

### FIXED CODE ###

import re, sys
print sum(map(int,re.sub(r"[^\d]+",r" "," ".join(sys.stdin.readlines())).strip().split()))
from collections import defaultdict

dp = {}
def util(adj, curr):
    res = 0
    if curr in dp:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next))
    dp[curr] = res
    return res

n, m = map(int, input().strip().split())
adj = defaultdict(list)
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)

lp = 0
for i in range(n):
    lp = max(lp, util(adj, i))
print(lp)

### FIXED CODE ###

import sys
sys.setrecursionlimit(11000)
def util(adj, curr, dp):
    res = 0
    if dp[curr] != -1:
        return dp[curr]
    for next in adj[curr]:
        res = max(res,1 + util(adj, next, dp))
    dp[curr] = res
    return res
 
n, m = map(int, input().strip().split())
adj = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().strip().split())
    adj[x - 1].append(y - 1)
dp = [-1]*n
lp = 0
for i in range(n):
    lp = max(lp, util(adj, i, dp))
print(lp)
#001
vowel = ['a','e','u','i','o']

x=raw_input()

if x in vowel:
    print("vowel")
else:
    print("consonant")

### FIXED CODE ###

vowel = 'aeuio'
x=raw_input()
if x in vowel:
    print("vowel")
else:
    print("consonant")
d,n = map(int,input())
ans = (100 ** d) * n
print(ans)

### FIXED CODE ###

d,n = map(int,input().split())
if n < 100:
  ans = (100 ** d) * n
  print(ans)
else:
  ans = (100 ** (d+1)) + 100 ** d
  print(ans)
results=[]
while True:
    a=input().split("\"")
    if a[0]==".":
        break
    b=input().split("\"")
    count1=0
    count2=0
    for i in range(int(len(a))):
        if(i%2==1):
            for k,l in zip(a[i],b[i]):
                if(k!=l):
                    count1+=1
        else:
            for k,l in zip(a[i],b[i]):
                if(k!=l):
                    count2+=1
    if len(a) != len(b):
        results.append(2)
    else:
        if count1==0 and count2==0:
            results.append(0)
        elif count1==1 and count2==0:
            results.append(1)
        else:
            results.append(2)
for i in results:
    if i==0:
        print("IDENTICAL")
    if i==1:
        print("CLOSE")
    if i==2:
        print("DIFFERENT")
    



### FIXED CODE ###

results=[]
while True:
    a=input().split("\"")
    if a[0]==".":
        break
    b=input().split("\"")
    count1=0
    count2=0
    if len(a) != len(b):
        results.append(2)
    else:
        for i in range(len(a)):
            if(i%2==1):
                if len(a[i]) != len(b[i]):
                    count1+=1
                else:
                    for k,l in zip(a[i],b[i]):
                        if(k!=l):
                            count1+=1
            else:
                if len(a[i]) != len(b[i]):
                    count2+=1
                else:
                    for k,l in zip(a[i],b[i]):
                        if(k!=l):
                            count2+=1           
        if count1==0 and count2==0:
            results.append(0)
        elif count1==1 and count2==0:
            results.append(1)
        else:
            results.append(2)
for i in results:
    if i==0:
        print("IDENTICAL")
    if i==1:
        print("CLOSE")
    if i==2:
        print("DIFFERENT")
# -*- coding: <encoding name> -*-

a, b, c = map(int, input())
print('a' if b ==c else 'b' if c == a else 'c')

### FIXED CODE ###

# -*- coding: <encoding name> -*-

a, b, c = map(int, input().split())
print(a if b ==c else b if c == a else c)
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))

nowa = 0
nowb = 0

li = []
total = 0

while total <= k:
    if nowa == n and nowb == m:
        break
    if nowa == n and nowb < m:
        total += b[nowb]
        li.append(b[nowb])
        nowb += 1
    elif nowa < n and nowb == m:
        total += b[nowb]
        li.append(b[nowb])
        nowa += 1  
    elif a[nowa] <= b[nowb]:
        total += a[nowa]
        li.append(a[nowa])
        nowa += 1
    elif a[nowa] > b[nowb]:
        total += b[nowb]
        li.append(b[nowb])
        nowb += 1

if sum(li) <= k:
    print(len(li))
else:
    print(len(li)-1)

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
from itertools import accumulate
import bisect

n,m,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(map(int,stdin.readline().rstrip().split()))

aa = [0]+list(accumulate(a))
bb = [0]+list(accumulate(b))
ma = 0

for i,j in  enumerate(aa):
    if j > k:
        break
    nowa = i
    nowb = bisect.bisect(bb,k-j)-1
    ma = max(ma,nowa+nowb)

print(ma)
N, A, B = map(int(input().split()))
print(min(N*A, B))
              

### FIXED CODE ###

N, A, B = map(int, input().split())
print(min(B, A*N))
import numpy as np
N, W = map(int, input().split())

items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.zeros(W+1)

for i, (w, v) in enumerate(items):
    tmp = np.zeros(W+1)
    tmp[w:] = dp[:-w] + v
    dp[w:] = np.fmax(tmp[w:], dp[w:])

print(int(dp[-1]))


### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())

items = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.full(N*1000 +1, W+1) #横軸を価値の値に変換する
dp[0] = 0

for i, (w, v) in enumerate(items):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

print(np.max(np.where(dp <= W)))
from heapq import *

INF = 10**15

def djikstra(G,s,d):
    #d = [0]*V
    que = []
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        c,v = heappop(que)
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

S = [INF]*V
T = [INF]*V
djikstra(Ga,s-1,S)
djikstra(Gb,t-1,T)
M = [0]*n
for i in range(n):
M[i] = INF-S[i]-T[i]
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])


### FIXED CODE ###

from heapq import *
from numpy import array,inf


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


n,m,s,t = map(int,input().split())
V = n
Ga = [[] for i in range(n)]
Gb = [[] for i in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    Ga[u-1].append((v-1,a))
    Ga[v-1].append((u-1,a))
    Gb[u-1].append((v-1,b))
    Gb[v-1].append((u-1,b))

S = djikstra(Ga,s-1)

T = djikstra(Gb,t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

for i in range(n):
    print(ans[i])