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

import numpy as np
from numba import jit
@jit(cache=True)
def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
A=np.array(A)
x=solve(n,k,A)
print(*x)


### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
c = Counter(A)
result = 0
piyo = []
for k, v in c.items():
    if v > 1:
        piyo.append(k)
        A.remove(k)
for a in A:
    flag = False
    for hoge in piyo:
        if a % hoge == 0:
            flag = True
            break
    if not flag:
        piyo.append(a)
        result += 1
print(result)

### FIXED CODE ###

def main():
    from collections import Counter
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    flag = [True] * (A[-1] + 1)
    for i in A:
        if flag[i]:
            result += 1
            for j in range(2*i, A[-1] + 1, i):
                flag[j] = False
    for k, v in c.items():
        if v > 1:
            if flag[k]:
                result -= v
    print(result)
main()
### BUGGY CODE ###

N, M = map(int, input().split())
A, C = [], []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C.append(sum(2 ** (i - 1) for i in map(int, input().split())))

table = [float('inf')] * 2 ** N
table[0] = 0
for m in range(M):
    for x in range(2 ** N):
        an = x | C[m]
        table[an] = min(table[an], table[an], table[x] + A[m])
ans = table[2 ** N - 1]

print(ans if ans != float('inf') else -1)


### FIXED CODE ###

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

p2 = 2 ** N
table = [10 ** 9] * p2
table[0] = 0
for m in range(M):
    a, _ = map(int, input().split())
    c = sum(2 ** (i - 1) for i in map(int, input().split()))
    for x in range(p2):
        an = x | c
        table[an] = min(table[an], table[x] + a)
ans = table[p2 - 1]
 
print(ans if ans != 10 ** 9 else -1)
### BUGGY CODE ###

s = input()
q = int(input())

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0
chs = ""
s_flip = False
ins = 0
while idx < q:
    if t[idx] == 1:
        flip = True
        while idx + 1 < q and t[idx + 1] == 1:
            idx += 1
            flip = not flip
        if flip:
            chs = chs[::-1]
            ins = len(chs) - ins
            s_flip = not s_flip
    else:
        if f[idx] == 1:
            ch = c[idx]
            while idx + 1 < q and t[idx + 1] == 2 and f[idx + 1] == 1:
                idx += 1
                ch = c[idx] + ch
            chs = ch + chs
            ins += len(ch)
        else:
            ch = c[idx]
            while idx + 1 < q and t[idx + 1] == 2 and f[idx + 1] == 2:
                idx += 1
                ch = ch + c[idx]
            chs = chs + ch
    idx += 1

ans = chs[:ins]
ans += s[::-1] if s_flip else s
ans += chs[ins:]
print(ans)



### FIXED CODE ###

s = input()
q = int(input())

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0

p = ""
while idx < q:
    if t[idx] == 1:
        s, p = p, s
    else:
        if f[idx] == 1:
            p += c[idx]
        else:
            s += c[idx]
    idx += 1

p = p[::-1]
s = p + s
print(s)
### BUGGY CODE ###

n = int(raw_input())
total = 0
for i in xrange(1, n+1):
  total += i % (i+1) if i < n else 0
print total

### FIXED CODE ###

n = int(raw_input())
print (n*(n-1))/2
### BUGGY CODE ###

S = input()
mod = 2019
cnt = [0]*mod
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    cnt[n%mod] += 1
    t *= 10
print(sum(i*(i-1)//2 for i in cnt))


### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7
res = 2**n - 1 

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod

res -= cmb(n,a,mod)
res -= cmb(n,b,mod)

print(res % mod)


### FIXED CODE ###

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

mod = 10**9 + 7
res = pow(2, n, mod)

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


A = cmb(n, a, mod)
B = cmb(n, b, mod)

print((res - A - B - 1) % mod)
### BUGGY CODE ###

N = int(input())
b = [int(x) for x in input().split()]
li=[]
def dfs(B,li):
    if(B == []):
        return True
    for index,i in enumerate(B):
        if(index == i-1):
            if(index == 0):
                if(dfs(B[1:],li)):
                    li.append(i)
                    return True
            else:
                if(dfs(B[:index]+B[index+1:],li)):
                    li.append(i)
                    return True
    return False

if(dfs(b,li)):
    for i in li:
        print(i)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
b = [int(x) for x in input().split()]
li=[]
def dfs(B,li):
    cand = []
    if(B == []):
        return True
    if(max(B)>len(B)):
        return False
    for i in range(1,len(B)+1):
        if(i in B):
            if(B.index(i)+1<i):
                return False
            elif(B.index(i)+1==i):
                cand.append(i)

    for i in cand:
        if(dfs(B[:i-1]+B[i:],li)):
            li.append(i)
            return True

    return False

if(dfs(b,li)):
    for i in li:
        print(i)
else:
    print(-1)
### BUGGY CODE ###

import copy
n = int(input())
lis = list(map(int,input().split()))

ans = {}
for i in lis:
    if i in ans:
        ans[i] += 1
    else:
        ans[i] = 1

for j in range(n):
    ans_t = copy.copy(ans)
    ans_t[lis[j]] -= 1
    su = 0
    for k in ans_t.values():
        su += (k - 1) * k // 2
    print(su)
    

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    lis = list(map(int,input().split()))
    d = Counter(lis)
    su = 0
    for e in d:
        su += (d[e] - 1) * d[e] // 2

    for e in lis:
        if d[e] <= 1:
            print(su)
        else:
            k = d[e]
            res = su - k*(k-1)//2 + (k-1)*(k-2)//2
            print(res)

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

import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp=[0]*N
 
for i in range(1,N):
	dp[i] = min(
		dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
	)

print(dp[N-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))

	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
		)
	print(dp[N-1])
main()
### BUGGY CODE ###

n,q = map(int, input().split())
 
tree = dict()
for i in range(n-1):
  a,b = map(int, input().split())
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for i in range(q):
  p,x = map(int, input().split())
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

print(*ans)

### FIXED CODE ###

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

n,q = map(int, input().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:n+n-2])
PX = iter(ABPX[n+n-2:])

tree = dict()
for a,b in zip(AB,AB):
  if a in tree: tree[a].add(b)
  else: tree[a] = {b}
  if b in tree: tree[b].add(a)
  else: tree[b] = {a}

opr = {i+1:0 for i in range(n)}
for p,x in zip(PX,PX):
  opr[p] += x

stack = [1]
parent = [0] * (n+1)
ans = [0]*n
while stack:
  x = stack.pop()
  ans[x-1] += opr[x]
  for y in tree[x]:
    if y == parent[x]: continue
    parent[y] = x
    stack.append(y)
    ans[y-1] += ans[x-1]

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)

ansSum = 0
for i in range(n-k+1):
    List = p[i:i+k]
    Sum = sum(List)
    if Sum > ansSum:
        ansSum = Sum
        ansList = List

ans = 0
for j in ansList:
    ans += l[j-1]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = []
y = 0
for x in range(1, 1001):
    y += x
    l.append(y/x)
m = []
for i in p:
    m.append(l[i-1])
s = [0]
z = 0
for i in m:
    z += i
    s.append(z)
ans = 0
for i in range(n-k+1):
    ans = max(ans, s[i+k] - s[i])
print(ans)
### BUGGY CODE ###

def resolve():
    from collections import deque
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    sA = 1
    s = deque()
    for i in range(K):
        s.append(A[i])
        sA *= A[i]
    tmp = sA
    for i in range(K, N):
        sA //= s.popleft()
        s.append(A[i])
        sA *= A[i]
        if tmp < sA:
            print("Yes")
        else:
            print("No")
        tmp = sA


resolve()


### FIXED CODE ###

def resolve():
    from collections import deque
    N, K = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    for i in range(K, N):
        if A[i - K] < A[i]:
            print("Yes")
        else:
            print("No")


resolve()
### BUGGY CODE ###

import collections
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

m = int(input())
a = list(map(int,input().split()))[:m]
c = collections.Counter(a)

memo = {}
rmemo = {}

for i in a:
    if rmemo.get(i):
        print(rmemo[i])
        continue

    res = 0
    for k,v in c.items():
        if i == k: v -= 1
        
        if v >= 2:
            if not memo.get(v):
                memo[v] = combinations_count(v, 2)

            res += memo[v]

    rmemo[i] = res
    print(res)

### FIXED CODE ###

import collections


m = int(input())
A = list(map(int,input().split()))[:m]
c = collections.Counter(A)
 
def hoge(n):
    return n * (n - 1) // 2

full = sum([ hoge(i) for i in c.values()])

for a in A:
    print(full - hoge(c[a]) + hoge(c[a]-1))
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))
X_s=sorted(X)
for i,x in enumerate(X):
    t=X_s.index(x)
    X_s.pop(t)
    print(X_s[(N-1)//2])
    X_s.insert(t,x)

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
X_s=sorted(X)
ans1=X_s[N//2]
ans2=X_s[N//2-1]
for i in X:
    print(ans1*(i<=ans2) or ans2)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    d = 0
    k = 10 ** (i+1)
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])

### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])
### BUGGY CODE ###

N = int(input())
lst = list(map(int, input().split()))
cnt = 0
for i in range(N):
  if lst[i] == min(lst[:i+1]):
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
lst = list(map(int, input().split()))
cnt = 0
tempmin = lst[0]
for i in range(N):
  if lst[i] <= tempmin:
    cnt += 1
    tempmin = lst[i]
print(cnt)
### BUGGY CODE ###

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
for k in range(2, int(math.sqrt(N)) + 1):
    if N % k == 0:
        is_not_prime = True
        break
if is_not_prime:
    for i in range(1, int(N*0.5)):

        j = N/i
        if j.is_integer():

            if (i+int(j)) < a:
                a = i+int(j)
        if j < 1:
            break

    print(a - 2)
else:
    print(N - 1)

### FIXED CODE ###

import math

N = int(input())

a = pow(10,12)

is_not_prime = False
#for k in range(2, int(math.sqrt(N)) + 1):
#    if N % k == 0:
#        is_not_prime = True
#        break
#if is_not_prime:
for i in range(1, int(math.sqrt(N))+1):
    #print(i)
    j = N/i
    if j.is_integer():

        if (i+int(j)) < a:
            a = i+int(j)
    #if j < 2:
    #    break

print(a - 2)
#else:
#    print(N - 1)
### BUGGY CODE ###

from functools import lru_cache

N, K = map(int, input().split())
P = list(map(int, input().split()))


@lru_cache(maxsize=None)
def calc_exp(n: int):
    return sum(range(1, n + 1)) / n


exp = -1
for i in range(len(P)):
    if len(P[i:i + K]) == K:
        e = sum(map(calc_exp, P[i:i + K]))
        if e > exp:
            exp = e

print(exp)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = list(map(lambda x: (x + 1) / 2, P))

s = sum(P[:K])
ans = [s]
for prev_a, next_a in zip(P, P[K:]):
    s -= prev_a
    s += next_a
    ans.append(s)
print(max(ans))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n+1), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            max_value = max(x, y, z)
            min_value = min(x, y, z)
            if min_value*min_value >= m:
                break
            if max_value*max_value >= m:
                continue

            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    max_n = n
    max_n = math.sqrt(max_n)
    max_n = math.ceil(max_n)

    ans = [0] * 10050

    for i in range(1, max_n+1):
        for j in range(1, max_n+1):
            for k in range(1, max_n+1):
                v = i*i + j*j + k*k + i*j + j*k + k*i
                if v < 10050:
                    ans[v] += 1

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

    """
    p = itertools.combinations_with_replacement(range(1, max_n), 3)

    #print(len(list(p)))
    ans_list = []


    for v in p:

        x, y, z = v
        ans_cnt = 0
        ans_list.append(x * x + y * y + z * z + x * y + y * z + z * x)



        if ans == m:
            if x == y == z:
                ans_cnt += 1
            elif x == y or y == z or x == z:
                ans_cnt += 3
            else:
                ans_cnt += 6
    """


    """
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)
    """


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

import sys
import bisect

input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

Q_dic = {q: i for i, q in enumerate(Q_array)}

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        influence = Q_array[index_left:index_right]
        for i in influence:
            ans_array[Q_dic[i]] = x
        del Q_array[index_left:index_right]

for ans in ans_array:
    print(ans)

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

index_array = [i for i in range(Q)]

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        now_index = index_left
        while now_index < index_right:
            if index_array[now_index] == now_index:
                ans_array[now_index] = x
                index_array[now_index] = index_right
                now_index += 1
            else:
                old_index = now_index
                now_index = index_array[now_index]
                index_array[old_index] = now_index




for ans in ans_array:
    print(ans)
### BUGGY CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+1)
b = 0
for i, (x, h) in enumerate(xh):
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  for j in range(i, (bisect_right(xh, [x+2*D, float('inf')]))):
  	ds[j] += times*A
  b += times
print(b)

### FIXED CODE ###

from bisect import bisect_right

N, D, A = map(int, input().split())
xh = sorted([list(map(int, input().split())) for _ in range(N)])
ds = [0]*(N+2)
b = 0
for i, (x, h) in enumerate(xh, 1):
  ds[i] += ds[i-1]
  d = ds[i]
  if d>=h:
    continue
  h -= d
  times = h//A if h%A==0 else h//A+1
  ds[i] += times*A
  ds[bisect_right(xh, [x+2*D, float('inf')])+1] -= times*A
  b += times
print(b)
### BUGGY CODE ###

import heapq
def dijk(s,edge):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
s-=1
t-=1
edge1 = [[] for i in range(n)]
edge2= [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z,w = map(int,input().split())
    edge1[x-1].append([z,y-1])
    edge1[y-1].append([z,x-1])
    edge2[x-1].append([w,y-1])
    edge2[y-1].append([w,x-1])
en=dijk(s,edge1)
su=dijk(t,edge2)
ans=[]
aa=10**20
for i in range(n-1,-1,-1):
    aa=min(aa,en[i]+su[i])
    ans.append(10**15-aa)
for i in range(n-1,-1,-1):
    print(ans[i])


### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
def dijk(s,edge,n):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
def main():
    n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
    s-=1
    t-=1
    edge1 = [[] for i in range(n)]
    edge2= [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(m):
        x,y,z,w = map(int,input().split())
        edge1[x-1].append([z,y-1])
        edge1[y-1].append([z,x-1])
        edge2[x-1].append([w,y-1])
        edge2[y-1].append([w,x-1])
    en=dijk(s,edge1,n)
    su=dijk(t,edge2,n)
    ans=[]
    aa=10**20
    for i in range(n-1,-1,-1):
        aa=min(aa,en[i]+su[i])
        ans.append(10**15-aa)
    for i in range(n-1,-1,-1):
        print(ans[i])
if __name__=='__main__':
    main()