Harryxun/stf_run huggingface dataset:
# ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

rui=[]
for i in range(d):
    T=[0]
    for j in range(1,h*w,d):
        T.append(abs(Al[j][0]-Al[j+1][0])+abs(Al[j][1]-Al[j+1][1]))
    for j in range(len(T)-1):
        T[j+1]+=T[j]
    rui.append(T)
q=I()
for w in range(q):
    l,r=IL()
    idx=l%d
    li=l//d
    ri=r//d
    print(rui[idx][ri]-rui[idx][li])

### FIXED CODE ###

# ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

rui={}
for i in range(d):
    T=[0]
    for j in range(1,h*w+1-i-d,d):
        T.append(abs(Al[j+i][0]-Al[j+d+i][0])+abs(Al[j+i][1]-Al[j+d+i][1]))
    for j in range(len(T)-1):
        T[j+1]+=T[j]
    rui[(i+1)%d]=T
q=I()
for w in range(q):
    l,r=IL()
    idx=l%d
    if idx==0:
        li=l//d-1
        ri=r//d-1
    else:
        li=l//d
        ri=r//d
    print(rui[idx][ri]-rui[idx][li])
#include<stdio.h>
int main(void){
  int N, A, B, sum, ans = 0;
  scanf("%d %d %d", &N, &A, &B);
  for(int i=0;i<=N;i++){
    int j=i;
    sum=0;
    while(j!=0){
      sum=sum+(j%10);
      j=j/10;
    }
    if(sum>=A && sum<=B){
      ans=ans+i;
    }
  }
  printf("%d\n", ans);
  return 0;
}


### FIXED CODE ###

def main():
    N = int(input())
    music = []
    m_time = []
    for _ in range(N):
        a, b = input().split()
        music.append(a)
        m_time.append(int(b))
    X = input()
    ans = 0
    for i, a in enumerate(music):
        if a == X:
            for j in range(i+1, N):
                ans += m_time[j]
    print(ans)
main()
import collections
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0:
        groups[B] = groups[A]
    elif groups[B] != 0:
        groups[A] = groups[B]
    else:
        groups[A] = groups[B] = group_num
        group_num += 1
collection = collections.Counter(groups)
# print(collection)
print(collection.most_common()[0][1] if collection.most_common()[0][0] != 0 else collection.most_common()[1][1])

### FIXED CODE ###

from collections import Counter
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num_list = [[0]]
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0 and groups[B] != 0:
        if groups[A] != groups[B]:
            lower = min(groups[A], groups[B])
            higher = max(groups[A], groups[B])
            for i in group_num_list[higher]:
                groups[i] = lower
            tmp = group_num_list[higher]
            group_num_list[lower].extend(tmp)
            # del group_num_list[higher]
    elif groups[A] != 0:
        groups[B] = groups[A]
        group_num_list[groups[A]].append(int(B))
    elif groups[B] != 0:
        groups[A] = groups[B]
        group_num_list[groups[B]].append(int(A))
    else:
        groups[A] = group_num
        groups[B] = group_num
        group_num_list.append([int(A), int(B)])
        group_num += 1
counter = Counter(groups)
# print(collection)
# print(group_num_list)
if len(group_num_list) == 1:
    print(1)
elif int(counter.most_common()[0][0]) != 0:
    print(counter.most_common()[0][1])
else:
    print(counter.most_common()[1][1])
import math
def combinatorial(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, K = (int(x) for x in input().split())
for i in range(1, K+1):
    ans = combinatorial(K-1, i-1)*combinatorial(N-K+1, i)%(10**9+7)
    print(ans)


### FIXED CODE ###

import math
def combinatorial(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, K = (int(x) for x in input().split())
for i in range(1, K+1):
    if N-K+1 >= i:
        ans = combinatorial(K-1, i-1)*combinatorial(N-K+1, i)%(10**9+7)
    else:
        ans = 0
    print(ans)
print'A%sC'%'BRG'[input()/100+4>>4]

### FIXED CODE ###

print('A'+'BRG'[int(input())//100+4>>4]+'C')
import sys
input = sys.stdin.readline

x, y  = map(int, input().split())
li =[]
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(1, y+1):
        if j - li[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j - li[i][0] ]+ li[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[x][y])

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i], v[i] = map(int, input().split())
    
INF = 10 ** 15
dp = [[INF]*(10**5+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for sum_v in range(10**5+1):
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i][sum_v], dp[i][sum_v - v[i]]+w[i] )
        else:
            dp[i+1][sum_v] = dp[i][sum_v]

max_v =0
for sum_v in range(10**5+1):
    if dp[n][sum_v] <= W:
        max_v = sum_v

print(max_v)
a,b,c=map(int,input().split())
for i in range(a,b+1):
  if i<a+n or i>b-n:
    print(i)

### FIXED CODE ###

a,b,c=map(int,input().split())
if c>(b-a)//2:
  for i in range(a,b+1):
    print(i)
else:
  for i in range(a,a+c):
    print(i)
  for i in range(b-c+1,b+1):
    print(i)
l,r=map(int,input().split())
if r-l>=2019:
  print(0)
else:
  a=2019
  for i in range(l,r):
    for j in range(i+1,r+1):
      if i==l and j==i+1:
        a=min((i%2019)*(j%2019)%2019,a)
print(a)

### FIXED CODE ###

l,r=map(int,input().split())
if r-l>=2019:
  print(0)
else:
  a=2019
  for i in range(l,r):
    for j in range(i+1,r+1):
      a=min((i%2019)*(j%2019)%2019,a)
  print(a)
import math
MAX = 7400000
prime = [1]*MAX
prime[0] = prime[1] = 0
res = []
sq = int(math.sqrt(MAX))
for i in xrange(2, sq+1):
    q = len(res)
    if prime[i]:
        res.append(i)
        for j in xrange(i*i, MAX, i):
            prime[j] = 0
    prime[i] = q
for i in xrange(sq+1, MAX):
    q = len(res)
    if prime[i]:
        res.append(i)
    prime[i] = q

def solve(m, n):
    # [m,m*m)
    sat = [0]*(m*m)
    for i in xrange(m, m*m):
        if not sat[i]:
            if n == 0:
                return i
            n -= 1
            for j in xrange(i, m*m, i):
                sat[j] = 1
    # [m*m,\inf)
    idx = prime[m*m]
    print m*m, res[idx]
    return res[idx+n]
while 1:
    m, n = map(int, raw_input().split())
    print solve(m, n)

### FIXED CODE ###

import math
MAX = 7400000
prime = [1]*MAX
prime[0] = prime[1] = 0
res = []
sq = int(math.sqrt(MAX))
for i in xrange(2, sq+1):
    q = len(res)
    if prime[i]:
        res.append(i)
        for j in xrange(i*i, MAX, i):
            prime[j] = 0
    prime[i] = q
for i in xrange(sq+1, MAX):
    q = len(res)
    if prime[i]:
        res.append(i)
    prime[i] = q

def solve(m, n):
    # [m,m*m)
    sat = [0]*(m*m)
    for i in xrange(m, m*m):
        if not sat[i]:
            if n == 0:
                return i
            n -= 1
            for j in xrange(i, m*m, i):
                sat[j] = 1
    # [m*m,\inf)
    idx = prime[m*m]
    return res[idx+n]
while 1:
    m, n = map(int, raw_input().split())
    if m==0:
        break
    print solve(m, n)
import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [SEN]
    R = a[mid:right] + [SEN]
    i,j = 0,0
    for k in range(left, right):
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    counter += right - left
def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)



### FIXED CODE ###

import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [sentinel]
    R = a[mid:right] + [sentinel]
    i,j = 0,0
    for k in range(left, right):
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    counter += right - left
def mergeSort(a, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
if(A[-1]==0):
    print(0)
else:
    ans=1
    flag=0
    for i in range(N):
        ans=ans*A[i]
        if(ans>10**18):
            flag=1
            break
    if(flag==0):
        print(ans)
    else:
        print(-1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
if(A[-1]==0):
    print(0)
else:
    ans=1
    flag=0
    for i in range(N):
        ans=ans*A[i]
        if(ans>10**18):
            flag=1
            break
    if(flag==0):
        print(ans)
    else:
        print(-1)
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [[float("INF")]*(N+1) for _ in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][1] = HP[1][1]
for i in range(1,N):
    for j in range(1,N+1):
        if dp[i-1][j-1] <= HP[i][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i][1])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break


### FIXED CODE ###

N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1
#dp[i][j] -> i人目までみたとき、j人が座布団を積む場合の最小枚数
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break
A,B,C = map(int(input().slice()))

print(C,A,B)

### FIXED CODE ###

A,B,C = map(int, input().split())

print(C,A,B)
class Node():
    def __init__(self,index):
        self.index = index
        self.parent = self 

    @staticmethod
    def find_set(node):
        if node.parent == node:
            return node 
        return Node.find_set(node.parent)

    @staticmethod
    def union(node_a,node_b):
        root_a = Node.find_set(node_a)
        root_b = Node.find_set(node_b)
        if root_a != root_b:
            node_a.parent = root_b



if __name__ == "__main__":
    n,m = [int(val) for val in input().split()]
    
    persons = []
    count = []
    for i in range(n):
        persons.append(Node(i))
        count.append(0)
    
    for i in range(m):
        a,b = [int(val) for val in input().split()]
        if a > b:
            Node.union(persons[a-1],persons[b-1])
        else:
            Node.union(persons[b-1],persons[a-1])


    for idx,person in enumerate(persons):
        count[Node.find_set(person).index] += 1
    
    # print(count)
    result = max(count)
    print(result)



### FIXED CODE ###

class Node():
    def __init__(self,index):
        self.index = index
        self.parent = self 
        self.size = 1

    @staticmethod
    def find_set(node):
        if node.parent == node:
            return node 
        root = Node.find_set(node.parent)
        node.parent = root
        return root

    @staticmethod
    def union(node_a,node_b):
        root_a = Node.find_set(node_a)
        root_b = Node.find_set(node_b)
        if root_a != root_b:
            if root_a.size < root_b.size:
                root_a.parent = root_b
                root_b.size == root_a.size
            else:
                root_b.parent = root_a
                root_a.size += root_b.size



if __name__ == "__main__":
    n,m = [int(val) for val in input().split()]
    
    persons = []
    count = []
    for i in range(n):
        persons.append(Node(i))
        count.append(0)
    
    for i in range(m):
        a,b = [int(val) for val in input().split()]
        if a > b:
            Node.union(persons[a-1],persons[b-1])
        else:
            Node.union(persons[b-1],persons[a-1])


    for idx,person in enumerate(persons):
        count[Node.find_set(person).index] += 1
    
    # print(count)
    result = max(count)
    print(result)
H,A = int(input()),int(input())
if(H%A != 0): print((H//A) + 1)
else: print(H/A)

### FIXED CODE ###

import math
H,A = map(int,input().split())
print(math.ceil(H/A))
s = list(str(input()))
t = list(str(input()))
ans = []
an = 0
if len(s) < len(t):
    print("UNRESTORABLE")
    exit()
for i in range(len(s)-len(t)+1):
    cou = s[i:i+len(t)]
    for k in range(len(t)):
        if s[i+k] != t[k] and s[i+k] != "?" and t[k] != "?":
            break
        if k == len(t)-1:
            ans.append(s[:i]+t+s[i+len(t):])
for h in range(len(ans)):
    for f in range(len(s)):
        if ans[h][f] == "?":ans[h][f] = "a"
    ans[h] = "".join(ans[h])
ans.sort()
print(ans[0])

### FIXED CODE ###

s = list(str(input()))
t = list(str(input()))
ans = []
an = 0
if len(s) < len(t):
    print("UNRESTORABLE")
    exit()
for i in range(len(s)-len(t)+1):
    cou = s[i:i+len(t)]
    for k in range(len(t)):
        if s[i+k] != t[k] and s[i+k] != "?" and t[k] != "?":
            break
        if k == len(t)-1:
            ans.append(s[:i]+t+s[i+len(t):])
for h in range(len(ans)):
    for f in range(len(s)):
        if ans[h][f] == "?":ans[h][f] = "a"
    ans[h] = "".join(ans[h])
if ans == []:
    print("UNRESTORABLE")
    exit()
ans.sort()
print(ans[0])
(X,Y,Z,K) = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

delicious_list = []
for a in A[:min((1000,len(A)))]:
    for b in B[:min((1000,len(B)))]:
        for c in C[:min((1000,len(C)))]:
            delicious_list.append(a+b+c)
delicious_list.sort(reverse=True)
for i in range(K):
    print(delicious_list[i])

### FIXED CODE ###

lis = []
for i in range(5):
    lis.append(int(input()))
k = int(input())

flag_disconnectable = False
for i in range(5):
    for j in range(5):
        if i == j: continue
        if (lis[j]-lis[i]) > k:
            flag_disconnectable = True
            break

if flag_disconnectable:
    print(":(")
else:
    print("Yay!")
h,a=divmod(int(input()))
m,s=divmod(a)
print(h":"m":"s)

### FIXED CODE ###

h,a=divmod(int(input()), 3600)
m,s=divmod(a,60)
print("{}:{}:{}".format(h,m,s))
import statistics
import math

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

B = []
C = []
D = []
E = []
ureshimi = []
k = 0
l = 0

for i in range(N-3):
    BC = A[0 : i + 2]
    s = 0
    for j in range(k, i + 2):
        s += BC[j]
        if s + BC[j + 1] > sum(BC) / 2:
            k = j
            if BC[j + 1] / 2 >= sum(BC) / 2 - s:
                B = BC[0 : j + 1]
                C = BC[j + 1 : i + 2]
            else:
                B = BC[0 : j + 2]
                C = BC[j + 2 : i + 2]
            break
    DE = A[i + 2 : N + 1]
    s = sum(DE[0:l - i + 1])
    for j in range(l - i + 1, N - i - 2):
        s += DE[j]
        if j == N - i - 3:
            l = j + i
            D = DE[0 : j + 1]
            E = DE[j + 1 : N - i]
            break
        elif s + DE[j + 1] > sum(DE) / 2:
            l = j + i
            if DE[j + 1] / 2 >= sum(DE) / 2 - s:
                D = DE[0 : j + 1]
                E = DE[j + 1 : N - i]
            else:
                D = DE[0 : j + 2]
                E = DE[j + 2 : N - i]
            break
    ureshimi.append(max(sum(B), sum(C), sum(D), sum(E)) - min(sum(B), sum(C), sum(D), sum(E)))



print(min(ureshimi))

### FIXED CODE ###

import statistics
import math

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


ureshimi = []
k = 0
l = 2

B = 0
C = 0
D = 0
E = 0

sumBC = sum(A[0:2])
sumDE = sum(A) - sumBC

for i in range(2, N - 1):
    for j in range(k, i):
        if j == i - 1:
            k = j
            C = sumBC - B
            break
        elif B + A[j] >= sumBC / 2:
            if sumBC / 2 - B  > A[j] / 2:
                B += A[j]
                k = j + 1
                C = sumBC - B
                break
            else:
                k = j
                C = sumBC - B
                break
        B += A[j]
    for j in range(l, N):
        if j == N - 1:
            l = j
            E = sumDE - D
            break
        elif D + A[j] >= sumDE / 2:
            if sumDE / 2 - D > A[j] / 2:
                D += A[j]
                l = j + 1
                E = sumDE - D
                break
            else:
                l = j
                E = sumDE - D
                break
        D += A[j]
    ureshimi.append(max([B, C, D, E]) - min([B, C, D, E]))
    sumBC += A[i]
    sumDE -= A[i]
    D -= A[i]
        

print(min(ureshimi))
N = int(input())
inis = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
    s = list(input())
    if s[0] == "M" or s[0] == "A" or s[0] == "R" or s[0] == "C" or s[0] == "H":
        inis[s[0]] += 1

ans = 0
march = ["M","A","R","C","H"]
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if march[i] != march[j] and march[i] != march[k] and march[j] != march[k]:
                ans += inis[march[i]] * inis[march[j]] * inis[march[k]]

print(ans)

### FIXED CODE ###

N = int(input())
inis = {"M": 0, "A": 0, "R": 0, "C": 0, "H": 0}
for i in range(N):
    s = list(input())
    if s[0] == "M" or s[0] == "A" or s[0] == "R" or s[0] == "C" or s[0] == "H":
        inis[s[0]] += 1

ans = 0
march = ["M","A","R","C","H"]
for i in range(len(march)):
    for j in range(i, len(march)):
        for k in range(j, len(march)):
            if march[i] != march[j] and march[i] != march[k] and march[j] != march[k]:
                ans += inis[march[i]] * inis[march[j]] * inis[march[k]]

print(ans)
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
s=[input() for i in range(n)]

g=[[]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]=="1":
            g[i].append(j)

# print(g)
ans=-float('inf')
for i in range(n):
    itta=[0]*n
    d=deque([i])
    cnt=0
    while d:
        # print(d)
        cnt+=1
        for i in range(len(d)):
            tmp=d.popleft()
            if itta[tmp]==0:
                itta[tmp]=cnt
                for j in range(len(g[tmp])):
                    if itta[g[tmp][j]]==0:
                        d.append(g[tmp][j])
            elif itta[tmp]==cnt:
                continue
            else:
                cnt=-float('inf')
    ans=max(ans,cnt)
if ans==-float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
s=[input() for i in range(n)]

g=[[]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]=="1":
            g[i].append(j)

# print(g)
ans=-float('inf')
for i in range(n):
    itta=[0]*n
    d=deque([i])
    cnt=0
    while d:
        # print(d)
        cnt+=1
        for i in range(len(d)):
            tmp=d.popleft()
            if itta[tmp]==0:
                itta[tmp]=cnt
                for j in range(len(g[tmp])):
                    if itta[g[tmp][j]]==0:
                        d.append(g[tmp][j])
            elif itta[tmp]==cnt:
                continue
            else:
                cnt=-float('inf')
    ans=max(ans,cnt)
if ans==-float('inf'):
    print(-1)
else:
    print(ans)
R,G,B,N=map(int,input().split())

#R*r+G*g+B*b==n
ir= int(R/N)
ig=int(G/N)
ib=int(B/N)
s=0
for R in range(ir):
    for G in range(ig):
        if(R*r+G*g>N):
            break;
        if((N-R*r-G*g)%B==0):
            s+=1
print(s)


### FIXED CODE ###

R,G,B,N=map(int,input().split())

#R*r+G*g+B*b==n
ir=int(N/R)+1
ig=int(N/G)+1
ib=int(N/B)+1
s=0
for r in range(ir):
    for g in range(ig):
        if(R*r+G*g>N):
            break;
        if((N-R*r-G*g)%B==0):
            s+=1
print(s)
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
if n == m == 10 ** 5:
    from heapq import heappush, heappop

    N, M, S, T = n, m, s, t
    graph = [[] for _ in range(N + 1)]
    for u, v, a, b in zip(*[iter(uvab)] * 4):
        graph[u].append((v, a, b))
        graph[v].append((u, a, b))


    def dijkstra(start, mode):
        INF = 10 ** 15
        dist = [INF] * (N + 1)
        dist[start] = 0
        q = [(0, start)]
        while q:
            d, v = heappop(q)
            if dist[v] < d:
                continue
            for w, *a in graph[v]:
                d1 = d + a[mode]
                if dist[w] > d1:
                    dist[w] = d1
                    heappush(q, (d1, w))
        return dist


    d1 = np.array(dijkstra(S, 0))
    d2 = np.array(dijkstra(T, 1))

    d1 += d2
    answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
    print('\n'.join(answer.astype(str)))
    exit()
s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.int64)
b = np.array(uvab[3::4], np.int64)

yen_matrix = coo_matrix((a, (u, v)), shape=(n, n), dtype=float_)
snuuk_matrix = coo_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.read
sys.setrecursionlimit(10 ** 7)

import numpy as np
from heapq import heappush, heappop

N,M,S,T, *uvab = map(int,input().split())
graph = [[] for _ in range(N+1)]
for u,v,a,b in zip(*[iter(uvab)]*4):
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
print('\n'.join(map(str, answer.tolist())))