Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

for i in range (0, max(A)):
	print(A.count(i+1))

for i in range (max(A), N):
	print(0)

### FIXED CODE ###

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

K = [0]*N

for i in range (0, N-1):
	K[L[i]-1]+=1

print(*K, sep = "\n")
### BUGGY CODE ###

N = int(input())
S = [int(i) for i in input()]

ans = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      Flag1 = True
      Flag2 = False
      Flag3 = False
      for x in S:
        if Flag3:
          if x == k:
            ans += 1
            break
        if Flag2:
          if x == j:
            Flag2 = False
            Flag3 = True
        if Flag1:
          if x == i:
            Flag1 = False
            Flag2 = True

print(ans)

### FIXED CODE ###

N = int(input())
S = [int(i) for i in input()]

ans = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      Flag1 = True
      Flag2 = False
      Flag3 = False
      for x in S:
        if Flag3:
          if x == k:
            ans += 1
            break
        if Flag2:
          if x == j:
            Flag2 = False
            Flag3 = True
        if Flag1:
          if x == i:
            Flag1 = False
            Flag2 = True

print(ans)
### BUGGY CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
#S,T = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
A1 = 1
for i in A:
    A1 *= i
if A1 > 1*10**18:
    print("-1")
else:
    print(A1)
#cnt = 0
#cnt += 1



#print(N)
#print(S,T)
#print(A)
#print('Yes')
#print('No')

### FIXED CODE ###

import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
#S,T = map(int, input().split())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    sys.exit()
#A = [int(input()) for _ in range(N)]
A1 = 1
for i in A:
    A1 *= i
    if A1 > 10**18:
        print("-1")
        sys.exit()

print(A1)
#cnt = 0
#cnt += 1



#print(N)
#print(S,T)
#print(A)
#print('Yes')
#print('No')
### BUGGY CODE ###

from collections import deque
def ge(H,W):
    q = deque([(0,0)])
    while q:
        x,y = q.popleft()
        yield (x,y)
        if y == 0 and x+1 < W:
            q.append([x+1,y])
        if y+1 < H:
            q.append([x,y+1])

def solve(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    x,y = 0,0
    for x,y in ((xx,yy) for xx,yy in ge(H,W) if field[yy][xx] == "."):
        mi = space[y][x]
        for h in xrange(y,H):
            if(field[h][x] == "*"):
                break
            mi = min(mi, space[h][x])
            ans = max(ans, mi*(h-y+1))
            if (W-x)*(H-y) < ans:
                return ans
    return ans

while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    print solve(field,H,W)

### FIXED CODE ###

def re_push(stack,num):#re_push and return max
    count = 0
    pre = num
    ma = 0
    while True:
        count += 1
        cur = stack.pop()
        if cur <= num:
            ma = max(ma,(count-1) * pre)
            stack += [cur]
            stack += [num]*(count-1)
            break
        if cur < pre:
            ma = max(ma,(count-1) * pre)
            stack += [cur]*count
            count = 0
        pre = cur
    return ma
            
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    table = [[0]*(W+1) for _ in xrange(H)]
    for y in xrange(H-1,-1,-1):
        for x in (x for x in xrange(W-1,-1,-1) if field[y][x] != "*"):
            table[y][x] = table[y][x+1] + 1
    ma = 0
    for x in xrange(W):
        stack = [0,table[0][x]]
        for y in xrange(1,H):
            if table[y-1][x] > table[y][x]:
                ma = max(ma, re_push(stack,table[y][x]))
            stack.append(table[y][x])
        ma = max(ma, re_push(stack,0))
    print ma
### BUGGY CODE ###

import math

N = int(input())
upper = int(math.sqrt(N)) + 1
#print(upper)

for n in range(1,N+1):
    myans = 0
    for x in range(1, upper):
        for y in range(1, upper):
            if x**2 + y**2 + x*y < n:
                for z in range(1, upper):
                    if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    #print(x,y,z,x**2 + y**2 + z**2 + x*y + y*z + z*x)
                        myans += 1
    print(myans)

### FIXED CODE ###


N = int(input())
myans = [ 0 for n in range(N+1)]
upper = int(N**(2/3))
#print(upper)
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v < N+1:
                myans[v] += 1
#print(myans)
for a,b in enumerate(myans):
    if a != 0:
        print(b)
### BUGGY CODE ###

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

a=list(map(int,input().split()))
b=list(map(int,input().split()))

x=[0]*M
y=[0]*M
c=[0]*M

for i in range(M):
    x[i],y[i],c[i]=map(int,input().split())
min=a[0]+b[0]
min1=0
for i in range(A):
    for j in range(B):
        for t in range(M):
            if i+1==x[t] and j+1==y[t]:
                min1=a[i]+b[j]-c[t]
            else:
                min1=a[i]+b[j]
            if min >= min1:
                min = min1
print(min)


### FIXED CODE ###

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

a=list(map(int,input().split()))
b=list(map(int,input().split()))

price=[0]*(M+1)

price[0] = min(a)+min(b)

for i in range(M):
    x, y, c = map(int,input().split())
    price[i + 1] = a[x-1] + b[y-1] - c

print(min(price))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

n =int(input())

# 空白区切りの数列をリストに代入
k = list(input())
for i in range(n):
    k[i]= int(k[i])
answer = 0
for i in range(1000):
    a=i//100
    b=(i%100)//10
    c=i%10
    p=0
#    print(a,b,c,p,n)
    for j in range(p,n):
        if k[j] == a:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j]== b:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j]== c:
#            p = j+1
            answer += 1
#            print(i)
            break

print(answer)





### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
#import numpy as np

n =int(input())

# 空白区切りの数列をリストに代入
k = list(input())
for i in range(n):
    k[i]= int(k[i])
answer = 0
for i in range(1000):
    a=i//100
    b=(i%100)//10
    c=i%10
    p=0
#    print(a,b,c,p,n)
    for j in range(p,n):
        if k[j] == a:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j] == b:
            p = j+1
            break
    else:
        continue
    for j in range(p,n):
        if k[j] == c:
#            p = j+1
            answer += 1
#            print(i)
            break

print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg0,tg1 = mv_a_tgs.pop()
    mv_a(tg0,tg1)
  while len(mv_b_tgs):
    wp0,wp1 = mv_b_tgs.pop()
    mv_b(wp0,wp1)
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

### FIXED CODE ###

from collections import deque
 
 
walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

l = ins()
a = l
n = len(l)
x = 3 if a[n-1]=='1' else 1
#for i in range(1,n):
for i in range(n-2,-1,-1):
    if a[i]=='1':
        x = (2*x+3**(n-1-i))%R
print(x)


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

l = ins()
a = l[::-1]
n = len(l)
x = 3 if a[0]=='1' else 1
for i in range(1,n):
    if a[i]=='1':
        x = (2*x+pow(3,i,R))%R
print(x)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
i = 0


H.sort(reverse=True)

while K > 0 and len(H) > 0:
    H.pop(0)
    K -= 1

i += sum(H)

print(i)

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
i = 0

H.sort(reverse=True)

if len(H) <= K:
    print(i)
else:
    del H[:K]
    i += sum(H)
    print(i)
### BUGGY CODE ###

N = int(input())
A =list(map(int, input().split()))
Q = int(input())
for i in range(Q):
    B,C = (int(x) for x in input().split())
    for j in range(N):
        if A[j]==B:
            A[j]=C
    print(sum(A))


### FIXED CODE ###

# 371 ms, 27032 KB
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
 
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]
 
dic = {}
for aa in a:
    dic[aa] = dic.get(aa, 0) + 1
 
s = sum(a)
for i in range(q):
    if b[i] not in dic:
        print (str(s))
        continue
    s += (c[i]-b[i]) * dic[b[i]]
    dic[c[i]] = dic.get(c[i], 0) + dic[b[i]]
    del dic[b[i]]
    print(s)
### BUGGY CODE ###

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

s = []

for i in range(n):
	s.append(a[i])
	s.reverse()
s = map(str,s)
print(' '.join(s))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
q = a[-1]

s = []

for i in range(n):
	s.append(0)

if n%2==1:
	for i in range(n//2+1):
		s[i]=a[-1-2*i]
	for i in range(n//2):
		s[n//2+1+i]=a[2*i+1]
else:
	for i in range(n//2):
		s[i]=a[-1-2*i]
	for i in range(n//2):
		s[n//2+i]=a[2*i]
s = map(str,s)
print(" ".join(s))
### BUGGY CODE ###

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

count = 0
for i, elem in enumerate(p):
    if min(p[:i+1]) == elem:
        count += 1

print(count)


### FIXED CODE ###

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

count = 0
p_min = p[0]

for elem in p:
    if elem <= p_min:
        count += 1
        p_min = elem

print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print(-1 if ans1!=ans2 else max(0,-ans1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m,p=map(int,input().split())
edge = [[] for i in range(m)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[i]=[a-1,b-1,-c+p]
d=[float("inf")]*n
d[0]=0

for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    d[e1]=min(d[e1],d[e0]+e2)
ans1=d[-1]
for _ in range(n):
  for i in range(m):
    e0,e1,e2=edge[i]
    if d[e1]>d[e0]+e2:
      d[e1]=-float("inf")
ans2=d[-1]
print(-1 if ans1!=ans2 else max(0,-ans1))
### BUGGY CODE ###

import numpy as np
N = int(input())
As = np.array(list(map(int, input().split())))\

max_A = max(As)

ans = 0
for n in range(N):
    h = As[n]
    co = As.copy()
    co = co + h - np.array([abs(n-i) for i in range(N)])
    ans += np.sum(co==0)
print(ans//2)
    
    
    
    

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
L = [A[i]+i for i in range(N)]
R = [i-A[i] for i in range(N)]
c = Counter(R)

ans = 0
for l in L:
    ans += c[l]

print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(1,n+1):
    for j in range(1,n+1):
        if a[j-1]==i:
            b.append(j)
print(*b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[a[i]-1]=i+1
print(*b)
### BUGGY CODE ###

import math

a, b, n = list(map(int, input().split()))

m = 0

for x in reversed(range(1,n+1)):
    if m > a*x/b:
        break
    else:
        y = math.floor(a*x/b) - a * math.floor(x/b)
        if m < y:
            m = y

print(m)

### FIXED CODE ###

import math

a, b, n = list(map(int, input().split()))

m = 0
x = n

while x >= n-b:
    if m > (a*x) // b:
        break
    else:
        y =  math.floor((a * (x / b - math.floor(x / b))))
        if m < y:
            m = y
            x = b * math.floor(x / b) - 1
        else:
            x-=1  

print(m)
### BUGGY CODE ###

from collections import deque
def dfs(neigh,K):
    q = deque()
    q.append(K)
    visited = [False]*N
    d = [0]*N
    visited[K] = True
    while len(q)>0:
        p = q.pop()
        for i in range(len(neigh[p])):
            if neigh[p][i]==0 or visited[i]:
                continue
            d[i] = d[p]+neigh[p][i]
            visited[i] = True
            q.append(i)
    return d

N = int(input())
neigh = [[0 for i in range(N)] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    neigh[a-1][b-1] = c
    neigh[b-1][a-1] = c
Q,K = map(int,input().split())
d = dfs(neigh,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[x-1]+d[y-1])


### FIXED CODE ###

from collections import deque
def dfs(neigh,K):
    q = deque([K])
    d = [0]*N
    visited = [0]*N
    visited[K] = True
    while q:
        p = q.pop()
        for di,cost in neigh[p]:
            if visited[di]:
                continue
            d[di] = d[p]+cost
            visited[di] = True
            q.append(di)
    return d

N = int(input())
neigh = [[] for i in range(N)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    neigh[a-1].append((b-1,c))
    neigh[b-1].append((a-1,c))

Q,K = map(int,input().split())
d = dfs(neigh,K-1)
for i in range(Q):
    x,y = map(int,input().split())
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

from numba import jit

n,k=map(int,input().split())
P=list(map(int,input().split()))
P=[p-1 for p in P]
C=list(map(int,input().split()))

@jit
def main():
  ans=-float('inf')
  for si in range(n):
    x=si
    S=[]
    tot=0
    while True:
      x=P[x]
      S.append(C[x])
      tot+=C[x]
      if x==si:
        break
    l=len(S)
    t=0
    for i in range(l):
      t+=S[i]
      if i+1>k:
        break
      now=t
      if tot>0:
        e=(k-i-1)//l
        now+=tot*e
      ans=max(ans,now)
  return ans      


print(main())

### FIXED CODE ###

n,k=map(int,input().split())
P=list(map(int,input().split()))
P=[p-1 for p in P]
C=list(map(int,input().split()))

def main():
  ans=-float('inf')
  for si in range(n):
    x=si
    S=[]
    tot=0
    while True:
      x=P[x]
      S.append(C[x])
      tot+=C[x]
      if x==si:
        break
    l=len(S)
    t=0
    for i in range(l):
      t+=S[i]
      if i+1>k:
        break
      now=t
      if tot>0:
        e=(k-i-1)//l
        now+=tot*e
      ans=max(ans,now)
  return ans      


if __name__=='__main__':
  print(main())
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    h = list(map(int, input().rstrip().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j >= n:
                break
            dp[i+j] = min([dp[i+j], dp[i]+abs(h[i]-h[i+j])])
    print(dp[n-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

n, m, k = map(int, input().split())
FRIENDS = [[0]*n for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIENDS[a][b] = FRIENDS[b][a] = 1
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]

ans = []

for i in range(n):
    c_friends = sum(FRIENDS[i])
    c_member = uf.count_member(i)
    ans.append(c_member - c_friends - 1)

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

### FIXED CODE ###

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

n, m, k = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    inf = 10**15
    d = [inf]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = [0]*n
m = 10**15
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    m = min(m,r)

    res[i] = m

x = 10**15
for i in range(n):
    print(x - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)
### BUGGY CODE ###

from collections import Counter

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return Counter(a)

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

ans = 0

for i in a:
    ans += prime_factorize(i)[2]
print(ans)

### FIXED CODE ###

from functools import reduce
from operator import mul

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

ans = 0

for i in a:
    count = 0
    while i%2 == 0:
        count += 1
        i = i/2
    ans += count

print(ans)
### BUGGY CODE ###

import numpy as np
n=int(input())
f=np.zeros(n+1,dtype=np.int64)
num=list(range(n+1))
num=np.array(num)
for i in range(1,n+1):
    f[i::i]+=1
ans=np.sum(f*num)
print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())
num=list(range(1,n+1))
num=np.array(num)
x=n//num
ans=num*(x+1)*x/2
print(int(np.sum(ans)))
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
ans = list()

for i in range(N):
    cnt = S.count('W',0,i)
    cnt += S.count('E',i+1,N)
    ans.append(cnt)
print(min(ans))

### FIXED CODE ###

N = int(input())
S = input()
cnt = S.count('E',1,N)
ans = [cnt]

for i in range(1,N):
    if S[i-1] == 'W':cnt += 1
    if S[i] == 'E': cnt -=1
    ans.append(cnt)
print(min(ans))
### BUGGY CODE ###

N=int(input())
S=input()
ans=N*10
for i in range(N):
  n=S[:i].count('W')+S[i+1:].count('E')
  ans=n if n<ans else ans
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
count=S[1:].count('E')
ans=S[1:].count('E')
for i in range(N-1):
  count+=(S[i].count('W')-S[i+1].count('E'))
  ans=count if count<ans else ans
print(ans)