Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

adic = {}
bdic = {}
cdic = {}


setabc = list(sorted(list(set(a) | set(b) | set(c))))

setdict = {}
for i in range(len(setabc)):
    setdict.update({setabc[i]:i})
    

for i in range(len(a)):
    if setdict[a[i]] in adic:
        adic[setdict[a[i]]] =  adic[setdict[a[i]]] + 1 
    else:
        adic.update({setdict[a[i]]:1})

for i in range(len(b)):
    if setdict[b[i]] in bdic:
        bdic[setdict[b[i]]] =  bdic[setdict[b[i]]] + 1 
    else:
        bdic.update({setdict[b[i]]:1})

for i in range(len(c)):
    if setdict[c[i]] in cdic:
        cdic[setdict[c[i]]] =  cdic[setdict[c[i]]] + 1 
    else:
        cdic.update({setdict[c[i]]:1})

ami = min(adic.keys())
ama = max(adic.keys())
bmi= min(bdic.keys())
bma= max(bdic.keys())
cmi= min(cdic.keys())
cma= max(cdic.keys())

        
        
summer = 0
for i in range(ami,ama+1):
    for j in range(bmi,bma + 1):
        if i < j:
            for k in range(cmi,cma+1):
                if i< j< k:
                    summer = summer + adic[i] * bdic[j] * cdic[k] 
                
print(summer)
                
    
            

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
#アルゴリズムわからないけどN log N?
a.sort()
b.sort()
c.sort()
 
#O(N)?
i,j,k = 0,0,0
ans = 0
while j < N:
  while i < N and a[i]<b[j] :
    i += 1
  while k < N and c[k]<=b[j]:
    k += 1
  ans += i * (N - k)
  j += 1
 

print(ans)
s = input()
ans = False
if s[0] == s[1] :
  if s[0] != s[2] and s[2] ==s[3] :
    ans = True
elif s[0] == s[2] :
  if s[0] != s[1] and s[1] ==s[3] :
    ans = True
else s[0] == s[3] :
  if s[0] != s[1] and s[2] ==s[1] :
    ans = True
if ans :
  print('Yse')
else:
  print('No')

### FIXED CODE ###

s=input()
ans=False
if s[0]==s[1]:
    if s[0]!=s[2] and s[2]==s[3]:
        ans=True
elif s[0]==s[2]:
    if s[0]!=s[1] and s[1]==s[3]:
        ans=True
elif s[0]==s[3]:
    if s[0]!=s[1] and s[1]==s[2]:
        ans=True
if ans:
    print('Yes')
else:
    print('No')
print(int(input) * 3.1415 * 2)

### FIXED CODE ###

print(int(input()) * 3.1415 * 2)
import math
from sys import stdin
input = stdin.readline
def main():
  A,B,N=map(int,input().split())
  sMax=0
  sCount=0
  sTgt_past=0
  if(N//B>=1):
    print(A-1)
  else:
    for i in range(1,B):
      sTgt=(A*i//B)-A*(i//B)
      if(i==1):
        sMax=sTgt
      else:
        sMax=max(sMax,sTgt)
      sTgt_past=sMax
    print(int(sMax))
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  K=int(input())
  A,B=map(int, input().split())
  for i in range(A,B+1):
    sTgt=i
    if(i%K==0):
      print('OK')
      break
    elif(i==B):
      print('NG')
  
if __name__=='__main__':
  main()
a,b,cmap(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-a+b)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-(a-b))
x,a=map(int,input().split())
if x>a
 print("0")
else x<=a
 print("10")

### FIXED CODE ###

x,a=map(int,input().split())
print(0 if x<a else 10)
def main():
    n, m = map(int, input().split())
    s = [0] * n
    c = [0] * n
    for i in range(m):
        s[i], c[i] = map(int, input().split())
    ans = list()
    for i in range(n):
        ans.append(0)
    for i in range(m):
        if n != 1 and s[i] == 1 and c[i] == 0:
            print(-1)
            exit()
        if ans[s[i]-1] == 0:
            ans[s[i]-1] = c[i]
        elif ans[s[i]-1] != 0 and ans[s[i]-1] == c[i]:
            continue
        elif ans[s[i]-1] != 0 and ans[s[i]-1] != c[i]:
            print(-1)
            exit()
    if n != 1:
        if ans[0] == 0:
            ans[0] = 1
        print(*ans, sep='')

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    s = [0] * m
    c = [0] * m
    for i in range(m):
        s[i], c[i] = map(int, input().split())
    ans = list()
    for i in range(n):
        ans.append(0)
    for i in range(m):
        if n != 1 and s[i] == 1 and c[i] == 0:
            print(-1)
            exit()
        if ans[s[i]-1] == 0 or ans[s[i]-1] == c[i]:
            ans[s[i]-1] = c[i]
        elif ans[s[i]-1] != 0 and ans[s[i]-1] != c[i]:
            print(-1)
            exit()
    if n != 1:
        if ans[0] == 0:
            ans[0] = 1
        print(*ans, sep='')
    else:
        print(*ans, sep='')

if __name__ == '__main__':
    main()
import math
n,x=map(int,input().split())
h=[int(i) for i in input().split()]
tmp=abs(x-h[0])
for q in range(1,n-1):
    tmp=math.gcd(abs(x-h[q]),tmp)
print(tmp)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
n,x=map(int,input().split())
h=[abs(x-int(a)) for a in input().split()]
print(reduce(gcd,h))
import sys
N, L, T = [int(x) for x in input().strip().split(" ")]

xys = []
candidates = []
for line in sys.stdin:
    x, y = line.strip().split(" ")
    x, y = int(x), int(y)
    xys.append((x,y))
    candidates.append((x + (1 if y == 1 else -1) * T)%L)

x0, y0 = xys[0]

dxs = []
pr_x = None
counter = 0
for x, y in xys[1:]:
    if y != y0:
        if pr_x == None:
            if y0 == 1:
                a = (x - x0)
        else:
            dxs.append(x - pr_x)
        pr_x = x
        counter += 1
if y0 == 2:
    a = (L - pr_x) + x0

ree = (2*T)%L
num_round = (2*T)//L
ree = ree - a
if ree < 0:
    max_i = 0
else:
    for i, dx in enumerate(dxs if y0 == 1 else dxs[::-1]):
        ree = ree - dx
        if ree < 0:
            max_i = i + 1
            break
    else:
        max_i = counter

c_n = num_round * counter + max_i

rep = ( 
        ((1 if y0 == 1 else -1) * (c_n % N) % N),
        ((x0 + (1 if y0 == 1 else -1) * (T % L)) % L)
        )
result = []

for i, c in enumerate(candidates):
    if c == rep[1]:
        start = i - rep[0]

for i in range(N):
    if ree != 0:
        print(candidates[(start + i) % N])
    else:
        print(candidates[(start + i) % N])


### FIXED CODE ###


import sys
N, L, T = [int(x) for x in input().strip().split(" ")]

xys = []
candidates = []
for line in sys.stdin:
    x, y = line.strip().split(" ")
    x, y = int(x), int(y)
    xys.append((x,y))
    candidates.append((x + (1 if y == 1 else -1) * T)%L)

x0, y0 = xys[0]

dxs = []
pr_x = None
counter = 0
for x, y in xys[1:]:
    if y != y0:
        if pr_x == None:
            if y0 == 1:
                a = (x - x0)
        else:
            dxs.append(x - pr_x)
        pr_x = x
        counter += 1

if pr_x == None:
    for x in candidates:
        print(x)
    sys.exit()
if y0 == 2:
    a = (L - pr_x) + x0

ree = (2*T)%L
num_round = (2*T)//L
ree = ree - a
if ree <= 0:
    max_i = 0
else:
    for i, dx in enumerate(dxs if y0 == 1 else dxs[::-1]):
        ree = ree - dx
        if ree <= 0:
            max_i = i + 1
            break
    else:
        max_i = counter

if ree == 0 and y0 == 2:
    max_i += 1

c_n = num_round * counter + max_i

rep = ( 
        ((1 if y0 == 1 else -1) * (c_n % N) % N),
        ((x0 + (1 if y0 == 1 else -1) * (T % L)) % L)
        )


candidates = sorted(candidates)

for i, c in enumerate(candidates):
    if c == rep[1]:
        start = i - rep[0]
        break

for j in range(N):
    print(candidates[(start + j) % N])
N=int(input())
List=list(map(int,input().split()))
Flag=0
Counter=-1
Element=0
while Flag<1:
  while Element<N:
      if List[Element]%2==1:
        Flag=1
      List[Element]=List[Element]/2
      Element+=1
  Element=0
  Counter+=1
print(Counter)

### FIXED CODE ###

s=input()
C=0
N=0
while C<3:
  if s[C]=="1":
    N+=1
  C+=1
print(N)
n = int(raw_input())

ans = 100000

d = []

for a in range(1,7):d.append( 6**a )
for a in range(1,6):d.append( 9**a )
d.append(1)
d.sort()
print d

dp = [1000000000] * 100000
dp[0] = 0
for x in range(0,n+1):
  for y in d:
    if x-y >= 0:
      dp[x] = min( dp[x-y] + 1, dp[x] )

print dp[n]


### FIXED CODE ###

n = int(raw_input())

ans = 100000

d = []

for a in range(1,7):d.append( 6**a )
for a in range(1,6):d.append( 9**a )
d.append(1)
d.sort()
#print d

dp = [1000000000] * 100001
dp[0] = 0
for x in range(0,n+1):
  for y in d:
    if x-y >= 0:
      dp[x] = min( dp[x-y] + 1, dp[x] )

print dp[n]
n, r = map(int, input().split())
if n >=10:
    print(r)
else:
    print(r + 100*(10-n))

### FIXED CODE ###

a,b,c = input().split()
print(c,a,b)
import math

def main():
  R = input()
  if 1 <= R <= 100:
    answer = float(R) * 2 / math.pi
  else:
    main()
  print(answer)
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

import math

def main():
  R = input()
  answer = float(R) * 2 * math.pi  
  print(answer)
  
if __name__ == '__main__':
  main()
import numpy as np

n=int(input())
xy=[]
for i in range(n):
    xy.append(list(map(int,input().split())))

def naiseki(a,b):
    if (a[0]*b[0]+a[1]*b[1])>0.0:
        return True
    else:
        return False
    
ans=0

for i in range(10001):
    x=np.cos(np.pi*2.0*i/10000.0)
    y=np.sin(np.pi*2.0*i/10000.0)
    for j in range(n):
        if i!=j and naiseki(xy[i],xy[j]):
            x+=xy[j][0]
            y+=xy[j][0]
    ans=max(ans,np.sqrt(x**2+y**2))
print(ans)


### FIXED CODE ###

import numpy as np

n=int(input())
xy=[]
for i in range(n):
    xy.append(list(map(int,input().split())))

def naiseki(a,b):
    if (a[0]*b[0]+a[1]*b[1])>0.0:
        return True
    else:
        return False
    
ans=0

for i in range(1001):
    xl=np.cos(np.pi*2.0*i/1000.0)
    yl=np.sin(np.pi*2.0*i/1000.0)
    x=0
    y=0
    for j in range(n):
        if naiseki([xl,yl],xy[j]):
            x+=xy[j][0]
            y+=xy[j][1]
    ans=max(ans,np.sqrt(x**2+y**2))
print(ans)
a = list(map(int,input().split()))
sort(a)
if (a[0] == a[1] and a[1] != a[2]) or (a[0] != a[1] and a[1] == a[2]):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a = list(map(int,input().split()))
a.sort()
if (a[0] == a[1] and a[1] != a[2]) or (a[0] != a[1] and a[1] == a[2]):
  print("Yes")
else:
  print("No")
s = list(input())
t = list(input())

flag = 0
for i in range(len(s)):
    if s[i] == t[0]:
        for j in range(i+1, i+len(t)-1):
            if s[j] == '?':
                flag = 1
            else:
                flag = 0
                break
    
    if flag:
        s[i:i+len(t)+1] = t
        break

if flag == 0:
    print('UNRESTORABLE')
    exit()

for k in range(len(s)):
    if s[k] == '?':
        s[k] = 'a'


print(''.join(s))

### FIXED CODE ###

s = input()
t = input()

if len(t) > len(s):
    print('UNRESTORABLE')
    exit()

s = s[::-1]
t = t[::-1]

for i in range(len(s) - len(t) + 1):
    j = 0
    while True:
        if j == len(t):
            ans = s[:i] + t + s[i+len(t):]
            print(ans[::-1].replace('?', 'a', len(ans)))
            exit()
        if t[j] == s[i+j] or s[i+j] == '?':
            j += 1
        else:
            break
print("UNRESTORABLE")
a = list(map(int, input().split()))
res = 0
for i in range(len(a)):
	if a[i] == i:
		res = i + 1
        break
print(res)


### FIXED CODE ###

a = list(map(int, input().split()))
res = 0
for i in range(len(a)):
    if a[i] == 0:
        res = i + 1
        break
print(res)
import math
from scipy import optimize


def f1(sita,b,x):
    return b**2/4*math.sin(2*sita)*(math.sin(2*sita)**2 + 1)-x


def resolve():
    a,b,x=map(int,input().split())
    xx=x/a
    if xx<a*b/2:
        ans = optimize.fsolve(f1,math.pi/2,args=(b,xx),epsfcn=10**-8)
        print(math.degrees(ans[0]))
        pass
    elif xx==a*b/2:
        print(45)
    else:
        ts=a**2/(a*b-xx)/2
        print(90-math.degrees(math.atan(ts)))
        pass

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math

def resolve():
    a,b,x=map(int,input().split())
    xx=x/a
    
    if x==b*a**2:
        print(0)
    elif xx<a*b/2:
        ts=b**2/(xx)/2
        print(math.degrees(math.atan(ts)))
        
    elif xx==a*b/2:
        print(45)
    else:
        ts=a**2/(a*b-xx)/2
        print(90-math.degrees(math.atan(ts)))
if __name__ == "__main__":
    resolve()
S = input()

if int(S[0:2]) <= 12 and int (S[0:2]) > 0:
    if int(S[2:4]) > 0 and int(S[2:4]) <= 12:
        print("AMBIGUOUS")
    elif int(S[2:4]) > 0:
        print("MMYY")
        
elif int(S[2:4]) <= 12 and int(S[2:4]) > 0:
    if int(S[0:2]) > 0 and int(S[0:2]) <= 12:
        print("AMBIGUOUS")    
    elif int(S[0:2]) > 0:
        print("YYMM")

elif int(S[0:2]) >= 13 and int(S[0:2]) == 0:
    if int(S[2:4]) == 0:
        print("NA")

elif int(S[2:4]) >= 13 and int(S[2:4]) == 0
    if int(S[0:2]) == 0:
        print("NA")

### FIXED CODE ###

S = str(input())

if 12 >= int(S[0:2]) >= 1:

    if 12 >= int(S[2:4]) >= 1:
        print("AMBIGUOUS")

    else:
        print("MMYY")

else:
    if 12 >= int(S[2:4]) >= 1:
        print("YYMM")

    else:
        print("NA")
a, b = map(int, raw_input().split())

if a>b:
????print 'a > b'
elif a<b:
????print 'a < b'
elif a==b:????
  print 'a == b'

### FIXED CODE ###

a, b = map(int, raw_input().split())

if a>b:
  print "a > b"
if a<b:
  print "a < b"
if a==b:
  print "a == b"
import sys
sys.setrecursionlimit(10 ** 7)

#dfs
M = int(input())
L = []
for i in range(M):
    d, c = map(int, input().split())
    L.extend([d] * c)

answer = 0

def dfs(count, l):
    global answer
    if len(l) == 1:
        #print(count)
        answer = max(answer, count)
    else:
        i = 0
        sum = l[i] + l[i+1]
        result = l[:i] + [int(x) for x in list(str(sum))] + l[i+2:]
        #print(result)
        dfs(count+1, result)

dfs(0, L)
print(answer)


### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

M = ni()
D = [] ; C = []

for i in range(M):
    d, c = na()
    D.append(d)
    C.append(c)

D = np.array(D) ; C = np.array(C)
#桁数の9倍とそれぞれの数字の総和をx
x = C.sum() * 9 + (C * D).sum()
# 18以下で終了
answer = (x + 8) // 9 - 2
print(answer)
N = int(input())
a = list(map(int, input().split()))
b = 1
if 0 in a:
  b = 0
else:
  for i in range(N):
    b *= a[i]
    if b > 10 ** 18:
      b = 'out'

if b == 'out':
  print(-1)
else:
  print(b)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
n=int(input())
if n % 4 == 0 or n % 7 == 0:
  print("Yes");
else:
  while n > 0:
    n -= 4
    if n % 7 == 0:
      print("Yes");
      return
  print("No");
    


### FIXED CODE ###

n=int(input())
if n % 4 == 0 or n % 7 == 0:
	print("Yes");
else:
	while n > 0:
		n -= 4
		if n % 7 == 0:
			print("Yes")
			exit()
	print("No")
import math

N = int(input())
As = [int(elm) for elm in input().split(" ")] 

if N >= 3:
    L = []
    R = []

    gl = As[0]
    gr = As[N-1]
    L.append(gl)
    R.append(gr)

    for i in range(1, N-1):
        gl = math.gcd(gl, As[i]) 
        L.append(gl)

    for i in range(1, N-1):
        gr = math.gcd(gr, As[N-i-1])
        R.append(gr)

    for i in range(N):
        if i == 0:
            max_g = R[N-2]
        else:
            if i == N-1:
                cur_g = L[N-2]
            else:
                cur_g = math.gcd(L[i-1], R[N-2-i])
            max_g = max(max_g, cur_g)

    out = max_g
else:
    out = max(As)

print(out)

### FIXED CODE ###

#import math
from fractions import gcd

N = int(input())
As = [int(elm) for elm in input().split(" ")] 


def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass

if N >= 3:
    gs = []
    for i in range(0, (N//2)*2 , 2):
        g = gcd(As[i], As[i+1])
        gs.append(g)
    if N % 2 == 1:
        gs.append(As[N-1])

    while len(gs) != 2:
        #print(gs)
        new_gs = []
        N1 = len(gs)
        #print("len",len(gs), (N1//2)*2)
        for i in range(0, (N1//2)*2, 2):
            g = gcd(gs[i], gs[i+1])
            new_gs.append(g)
        if N1 % 2 == 1:
            new_gs.append(gs[-1])
        gs = new_gs

    g1, g2 = gs
    d1 = divisor(g1) 
    d2 = divisor(g2) 
    ds = sorted(d1 + d2, reverse=True)

    #print(gs)
    #print(ds)
    for d in ds:
        count = sum([int(A % d == 0) for A in As])
        if count >= N-1:
            out = d
            break

else:
    out = max(As)

print(out)
s = input()

for i in range(n):
  if s[i] == "A":
    l = i
    break
for i in range(n-1,-1,-1):
  if s[i] == "Z":
    r = i
    break
print(s[l:r+1])

### FIXED CODE ###

s = input()
n = len(s)
for i in range(n):
	if s[i] == "A":
		l = i
		break
for i in range(n-1,-1,-1):
	if s[i] == "Z":
		r = i
		break
print(r-l+1)
if W > S:
  return "unsafe"
else:
  return "safe"

### FIXED CODE ###

S, W = [int(x) for x in input().split()]
 
if W >= S:
  print('unsafe')
else:
  print('safe')
import numpy as np

[H, W, M] = map(int, input().split())
mp = np.zeros((H+1, W+1), dtype=np.int64)
for i in range(M):
    [h, w] = map(int, input().split())
    mp[h][w] = 1

#colsum = np.sum(mp, axis=0)
#rowsum = np.sum(mp, axis=1)

#maxcol = max(colsum)
#maxrow = max(rowsum)

#colchk = np.where(colsum==maxcol)
#rowchk = np.where(rowsum==maxrow)

#for i in range(len(rowchk[0])):
#    for j in range(len(colchk[0])):
#        if mp[rowchk[0][i]][colchk[0][j]] == 0:
#            print(int(max(colsum)+max(rowsum)))
#            quit()

print(int(max(colsum)+max(rowsum))-1)


### FIXED CODE ###

import numpy as np

[H, W, M] = map(int, input().split())
colsum = np.zeros(W+1)
rowsum = np.zeros(H+1)
bombs = []
rowbombs = [set() for i in range(H+1)]
for i in range(M):
    [h, w] = map(int, input().split())
    rowsum[h] += 1
    colsum[w] += 1
    bombs.append([h, w])
    rowbombs[h].add(w)

maxcol = max(colsum)
maxrow = max(rowsum)

colchk = np.where(colsum==maxcol)
rowchk = np.where(rowsum==maxrow)

for i in range(len(rowchk[0])):
    for j in range(len(colchk[0])):
        if colchk[0][j] not in rowbombs[rowchk[0][i]]:
            print(int(max(colsum)+max(rowsum)))
            quit()

print(int(max(colsum)+max(rowsum))-1)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = ZIP(N)
A = np.array(A)
B = np.array(B)
max_A = A.max()

L = H+1
dp = np.zeros(L, dtype=np.int64)

for i in range(1, H+1):
	dp[i]=(dp[i-A]+B).min()

print(dp[H])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))
#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

N,M=map(int,input().split())
a = list(map(int, input().split()))

lcm = 1
for A in a:
    a//=2
    lcm *=a//fractions.gcd(lcm, a)
    if lcm>0:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)


### FIXED CODE ###

#=============================================================================
#ABC150 D
#=============================================================================
import fractions
from functools import reduce

N,M=map(int,input().split())
a = list(map(int, input().split()))

lcm = 1
for A in a:
    A//=2
    lcm *=A//fractions.gcd(lcm, A)
    if lcm>M:
        print(0)
        exit()
for A in a:
    if lcm/A==int(lcm/A):
        print(0)
        exit()

cnt=M//lcm
print((cnt+1)//2)
S=input()
def union(s):
    answer_str = s
    for i in range(len(s)-1):
        if s[i]!=s[i+1]:
            if i!=len(s)-2:
                return union(s[:i]+s[i+2:])
            else:
                return union(s[:i])
    
    return answer_str
 
print(len(S)-len(union(S)))



### FIXED CODE ###

S=input()

zero_count=0
one_count=0
for c in S:
    if c=='1':
        one_count+=1
    else:
        zero_count+=1

print(min(zero_count,one_count)*2)
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m,s,t = map(int, input().split())
money = np.zeros((n+1,n+1))
snu = np.zeros((n+1,n+1))
for i in range(m):
    u,v,a,b = map(int, input().split())
    money[u][v] = money[v][u] = a
    snu[u][v] = snu[v][u] = b
money = dijkstra(csr_matrix(money))
snu = dijkstra(csr_matrix(snu))
start = 10**15
#何年目か？
for i in range(n):
    ans = 0
    #i年目なので、iまででは両替出来ない。両替する場所を探す
    for j in range(i+1,n+1):
        ans = max(ans, start - (money[s][j] + snu[j][t]))
    print(int(ans))

### FIXED CODE ###

import numpy as np
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
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

n,m,s,t = map(int, input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = map(int, input().split())
    graph[u].append([v,a,b])
    graph[v].append([u,a,b])
money = dijkstra(s,0)
snu = dijkstra(t,1)
start = 10**15
#何年目か？
ans = []
ans_max = 10**15
for j in range(n,-1,-1):
    ans_max = min(ans_max, (money[j] + snu[j]))
    ans.append(ans_max)
for i in range(n-1,-1,-1):
    print(int(start - ans[i]))