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

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
for t in range(m):
	b = a[0]//2
	del a[0]
	if len(a) == 0:
		a.append(b)
	elif b <= a[-1]:
		a.append(b)
	else:
		for s in range(n-1):
			if b >= a[s]:
				a.insert(s, b)
				break
print(sum(a))

### FIXED CODE ###

import bisect
n,m = map(int,input().split())
a = list(map(int,input().split()))
while m != 0:
    a.sort()
    where = bisect.bisect_left(a,a[-1]//2)
    where = abs(where-(n+1))
    for i in range(1,min(where,m+1)):
        a[-i] = a[-i]//2
        m = m-1
print(sum(a))
### BUGGY CODE ###

#152 Low Elements
n = int(input())
seq = list(map(int,input().split()))
num = 0
for i in range(1,n+1):
    test = seq[:i]
    if min(test) == seq[i-1]:
        num += 1
print(num)
    

### FIXED CODE ###

#152 Low Elements
n = int(input())
seq = list(map(int,input().split()))
c = []
cnt = 0
for i in range(n):
    if i == 0:
        cnt+=1
        c.append(seq[0])
    else:
        if c[-1] >= seq[i]:
            cnt += 1
            c.append(seq[i])
        
print(cnt)
### BUGGY CODE ###

N, K = map(int, raw_input().split())
x = [map(int, raw_input().split()) for i in range(N)]
ans = 10**30
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                x0, y0 = x[i]
                x1, y1 = x[j]
                x2, y2 = x[k]
                x3, y3 = x[l]
                x_min = min([x0, x1, x2, x3])
                x_max = max([x0, x1, x2, x3])
                y_min = min([y0, y1, y2, y3])
                y_max = max([y0, y1, y2, y3])
                cnt = 0
                for m in range(N):
                    x4, y4 = x[m]
                    if (x_min <= x4 <= x_max) and (y_min <= y4 <= y_max):
                        cnt += 1
                if cnt >= K:
                    S = (x_max - x_min) * (y_max - y_min)
                    ans = min(S, ans)
print ans

### FIXED CODE ###

n, k = map(int, raw_input().split())
p = [map(int, raw_input().split()) for i in range(n)]
p = sorted(p, key=lambda _: _[0])
ans = 10**30
for b in range(n):
    x_b, y_b = p[b]
    for t in range(n):
        x_t, y_t = p[t]
        if y_t <= y_b:
            continue
        v = filter(lambda _: y_b <= _[1] <= y_t, p)
        for i in range(len(v) - k + 1):
            x_i, y_i = v[i]
            x_j, y_j = v[i+k-1]
            ans = min(ans, (x_j - x_i) * (y_t - y_b))
print ans
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

dic = list(set(a))
count = 0
for x in dic:
    if a.count(x) > x:
        count+= a.count(x) - x
    elif a.count(x) < x:
        count += a.count(x)
print(count)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]


count = len([i for i in a if i > 10**5])
a = [e for e in a if e <= 10**5]
dic = list(set(a))
for x in dic:
    if a.count(x) > x:
        count+= a.count(x) - x
    elif a.count(x) < x:
        count += a.count(x)
print(count)
### BUGGY CODE ###

s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

### FIXED CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)
### BUGGY CODE ###

'''WA
N,K=map(int,input().split())
A=list(map(int,input().split()))
x=A.index(1)
K-=1
print((x-1)//K+(N-x-2)//K+2)
'''
N,K=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
while 1:
    idx=A.index(1)
    if idx==0:break
    if idx+1<=K:
        A[:K]=[1]*K
    else:
        A[idx-K+1:idx+1]=[1]*K
    cnt+=1
A=A[::-1]
while 1:
    idx=A.index(1)
    if idx==0:break
    if idx+1<=K:
        A[:K]=[1]*K
    else:
        A[idx-K+1:idx+1]=[1]*K
    cnt+=1
print(cnt)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
idx=A.index(1)
cnt=0
if idx:
    if idx+1<=K:
        cnt=1
        A[:K]=[1]*K
    else:
        cnt=(idx-1)//(K-1)+1
        num=cnt*(K-1)+1
        A[:num]=[1]*num
A=A[::-1]
idx=A.index(1)
if idx:
    if idx+1<=K:
        cnt+=1
        A[:K]=[1]*K
    else:
        cnt+=(idx-1)//(K-1)+1
        num=cnt*(K-1)+1
        A[:num]=[1]*num
print(cnt)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in A:
    ans = 0
else:
    for a in A:
        ans *= a
        if ans > 10**18:
            ans = -1
            break

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

n = int(input())
a = [int(i) for i in input().split()]
dic = {}
flag = 1
for i in range(n):
    if a[i] in dic.keys():
        flag = 0
        print("NO")
        break
    else:
        dic[a[i]] = 1
if flag:
    print("YES")


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
dic = {}
for i in range(n):
	try:
		dic[a[i]] += 1
	except:
		dic[a[i]] = 1
if max(dic.values()) > 1:
	print("NO")
else:
  	print("YES")
### BUGGY CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###二次元DP
# dp = [[0] * (h + 1) for i in range(n+1)]
# for i in range(n):
#     for j in range(h+1):
#         a = ab[i][0]
#         b = ab[i][1]
#         # print(i, j)
#         if i == 0:
#             if j <= a and j > 0:
#                 dp[i+1][j] = b
#             elif j > a:
#                 dp[i+1][j] = dp[i+1][j-a] + b
#         else:
#             if j <= a:
#                 dp[i+1][j] = min(dp[i][j], b)
#             else:
#                 dp[i+1][j] = min(dp[i][j], dp[i+1][j-a] + b)
# # for i in dp:
# #     print(i)
# print(dp[-1][-1])

#一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])


### FIXED CODE ###

h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
###一次元DP
dp = [100000000] * (h+1)
dp[0] = 0
for i in range(1, h+1):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        # print(i, j)
        temp = i - a
        if temp < 0:
            temp = 0
        need_magic = dp[temp] + b
        if need_magic < dp[i]:
            dp[i] = need_magic
        # dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
        # print(i, j, a, b, dp)
print(dp[-1])
### BUGGY CODE ###

n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = deque()
done = []
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b.appendleft(q)
    done.append(q)
    for new_q in g[q]:
        v_,d_ = new_q
        if v_ not in done:
            queue.appendleft([v_,d+d_])
for i in range(1,n+1):
    if i in b:
        print(1)
    else:
        print(0)

### FIXED CODE ###

n = int(input())
v = [list(map(int,input().split())) for _ in range(n-1)]
g = {}
for a,b,w in v:
    if a not in g:
        g[a] = []
    if b not in g:
        g[b] = []
    g[a].append([b,w])
    g[b].append([a,w])
from collections import deque
queue = deque([[1,0]])
b = [-1]*n
b[0] = 0
while queue:
    q,d = queue.popleft()
    if d%2==1:
        b[q-1] = 0
    else:
        b[q-1] = 1
    for new_q in g[q]:
        v_,d_ = new_q
        if b[v_-1]==-1:
            queue.appendleft([v_,d+d_])
for i in b:
    print(i)
### BUGGY CODE ###

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())

#output
import numpy as np
import bisect as bi

X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]

damage = np.zeros(N, int)
answer = 0

for i in range(N):
    if H[i] <= 0:
        continue
    else:
        J = (H[i]-1+A)//A
        damage[i] = J*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -J*A
    damage = np.cumsum(damage)
    answer += J
    H -= damage
    damage[i:a] = 0

print(answer)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N+1, int)
answer = 0
power = 0
for i in range(N):
    power -= damage[i]
    J = (H[i]-1+A)//A
    if J <= power:
        continue
    else:
        a = bi.bisect_right(X, X[i]+2*D)
        damage[a] += J - power
        answer += J-power
        power = J
 
print(answer)
### BUGGY CODE ###

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

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


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

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


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

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 ###

n,m = map(int,input().split())
res={i for i in range(1,n+1)}
for i in range(m):
	l,r = map(int,input().split())
	g = { i for i in range(l,r+1)}
	res = res&g
	if res == {} :
		print(0)
		break
print(len(res))

### FIXED CODE ###


n,m = map(int,input().split())
L = []
R = []
for i in range(m):
	l,r = map(int,input().split())
	L.append(l)
	R.append(r)

l = L[0]
r = R[0]
cnt = 0
for i in range(max(L),min(R)+1) :
	if 0<=i<=r :
		cnt += 1
print(cnt)
### BUGGY CODE ###

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
  	prod *= a
  if prod > 1000000000000000000:
    print(-1)
    return
  print(prod)
    
    
main ()


### FIXED CODE ###

def main ():
  N = int(input())
  A = list(map(int,input(). split ()))
  
  if 0 in A:
    print(0)
    return
  prod = 1
  for a in A:
    prod *= a
    if prod > 1000000000000000000:
      print(-1)
      return
  print(prod)
main ()
### BUGGY CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
total=w
for i in range(n):
    x,y=map(int,input().split())
    weight.append(x)
    value.append(y)
l=len(weight)
dp=[[0 for i in range(total+1)] for i in range(l)]
for i in range(l):
    for w in range(total+1):
        if weight[i]<=w:
            dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[l-1][total])

### FIXED CODE ###

import numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [[0]*(2*N0) for _ in range(26)]
lazy = [[0]*(2*N0) for _ in range(26)]

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(k, *ids):
    for i in reversed(ids):
        v = lazy[k][i-1]
        if not v:
            continue
        lazy[k][2*i-1] += v; lazy[k][2*i] += v
        data[k][2*i-1] += v; data[k][2*i] += v
        lazy[k][i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x, k):
    *ids, = gindex(l, r)
    propagates(k, *ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[k][R-1] += x; data[k][R-1] += x
        if L & 1:
            lazy[k][L-1] += x; data[k][L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[k][i-1] = max(data[k][2*i-1], data[k][2*i])

# 区間[l, r)内の最大値を求める
def query(l, r, k):
    propagates(k, *gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[k][R-1])
        if L & 1:
            s = max(s, data[k][L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for j in range(N):
    u = S[j]
    update(j, N, 1, ord(u) - ord_a)

Q = int(input())

for _ in range(Q):
    q = input().rstrip().split()
    if q[0] == "2":
        l, r = int(q[1]) - 1, int(q[2]) - 1
        cnt = 0
        for i in range(26):
            if l == 0:
                cnt += int(query(r, r + 1, i) > 0)
            else:
                cnt += int((query(r, r + 1, i) - query(l - 1, l, i) > 0))
        print(cnt)
    else:
        i, c = int(q[1]) - 1, q[2]
        update(i, N, -1, ord(S[i]) - ord_a)
        S[i] = c
        update(i, N, 1, ord(S[i]) - ord_a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bits = [Bit(N) for _ in range(26)]

for i in range(N):
    s = S[i]
    bits[ord(s) - ord_a].add(i + 1, 1)

Q = int(input())

for _ in range(Q):
    query = input().rstrip().split()
    if query[0] == "1":
        i, c = int(query[1]), query[2]
        bits[ord(S[i - 1]) - ord_a].add(i, -1)
        S[i - 1] = c
        bits[ord(S[i - 1]) - ord_a].add(i, 1)
    else:
        l, r = int(query[1]), int(query[2])
        res = 0
        for bit in bits:
            if l != 1:
                res += int(bit.sum(r) - bit.sum(l - 1) > 0)
            else:
                res += int(bit.sum(r) > 0)
        print(res)
### BUGGY CODE ###

def minus(n):
    return n-1

N, K, Q = map(int,input().split())

A_list = [int(input()) for i in range(Q)]
Point_list = [K for i in range(N)]

for j in range(Q):
    Point_list = list(map(minus,Point_list))
    Point_list[A_list[j]-1] += 1

for j in range(N):
    if Point_list[j] <= 0:
        print("No")

    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int,input().split())

A_list = [int(input()) for i in range(Q)]
Point_list = [K-Q for i in range(N)]

for j in range(Q):
    Point_list[A_list[j]-1] += 1

for j in range(N):
    if Point_list[j] <= 0:
        print("No")

    else:
        print("Yes")
### BUGGY CODE ###

# input
N, M = map(int, input().split())
check = {}
for i in range(1, M + 1):
    L, R = map(int, input().split())
    check[i] = set(list(range(L, R + 1)))

# check
mastar_keys = set(list(range(1, N + 1)))
for k in check.keys():
    mastar_keys = mastar_keys & check[k]

print(len(mastar_keys))

### FIXED CODE ###

# input & check
N, M = map(int, input().split())
x, y = 0, N
for i in range(1, M + 1):
    L, R = map(int, input().split())
    x = max(x, L)
    y = min(y, R)

print(len(range(x, y + 1)))
### BUGGY CODE ###

import math

n = int(input())

a=[]
prime=[]

for i in range(n+1):
    a.append(1)
    prime.append(0)

m=0
for i in range(2,n+1,1):
    if a[i]==1:
        m=m+1
        prime[m]=i
        for j in range(i,n+1,i):
            a[j]=0


yaku=[]
for i in range(n+1):
    yaku.append(0)

yaku[1]=1

for i in range(m,0,-1):
    p=prime[i]
    for j in range(int(n/p),0,-1):
        if yaku[j]>0:
            for k in range(1,1+int(math.log(n/j,p)),1):
                yaku[j*int(math.pow(p,k))]=yaku[j]*(k+1)


#print(yaku)

sum=0;
for i in range(1,n+1,1):
    sum+=i*yaku[i]

print(sum)



### FIXED CODE ###

n = int(input())
sum=0
for i in range(1,n+1,1):
    t=int(n/i)
    sum+=i*t*(t+1)/2

print(int(sum))
### BUGGY CODE ###

L, R = map(int, input().split())
min = 2020
for i in range(L, R+1):
    for j in range(i+1, R+1):
        if min > (i * j) % 2019:
            min = (i * j) % 2019
    if i == L + 2020:
        break
print(min)

### FIXED CODE ###

L, R = map(int, input().split())
m = 2020
import sys
for i in range(L, R+1):
    for j in range(i+1, R+1):
        if m > (i * j) % 2019:
            m = (i * j) % 2019
        if m == 0:
            print(0)
            sys.exit()
print(m)
### BUGGY CODE ###

N,W=map(int,input().split())

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = max(dp[c], profits + dp[c - weights])
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
ans=0
for i in A:
  if dp[i]==0:
    for j in range(i,10**6+1,i):
      dp[j]+=1
  else:
    dp[i]+=1
for i in A:
  if dp[i]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

#C
N = int(input())
P = list(map(int, input().split()))
ans = 0

for i in range(N):
    frag = True
    for j in range(i):
        if P[i] > P[j]:
            frag = False
            break
    if frag == True:
        ans += 1
        
print(ans)

### FIXED CODE ###

#C
N = int(input())
P = list(map(int, input().split()))
ans = 0
min_num = 10**6

for i in range(N):
    min_num = min(min_num, P[i])
    if min_num >= P[i]:
        ans += 1
        
print(ans)
### BUGGY CODE ###

import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in filter(lambda x: x[1] < inf, enumerate(graph[u])):
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [[inf for _ in range(n)] for _ in range(n)]
snuke_graph = [[inf for _ in range(n)] for _ in range(n)]

for i in range(m):
    u, v, a, b = map(int, next(sys.stdin).split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

for i in range(n):
    print(10**15 - min(total_costs[i:]))


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from itertools import accumulate
 
def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float("inf")):
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1
 
    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1
 
        dests = ((i, n) for i, n in enumerate(edges[v]) if n != default_value)\
            if adj_matrix else edges[v]
 
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))
 
    return vertices
 
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen = [[] for _ in [0]*n]
sno = [[] for _ in [0]*n]
for l in sys.stdin.readlines():
    u, v, a, b = map(int, l.strip().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    sno[u-1].append((v-1, b))
    sno[v-1].append((u-1, b))
 
yen = dijkstra(n, yen, s)
sno = dijkstra(n, sno, t)
result = list(accumulate([y+s for y, s in zip(yen, sno)][::-1], min))
money = 10**15
for n in result[::-1]:
    print(money-n)