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

N,K=map(int,input().split())
light=list(map(int,input().split()))
copy=[0]*N
for k in range(K):
  imo=[0]*(N+1)
  x=0
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
  for j in range(N):
    x+=imo[j]
    copy[j]=x
  if light==copy:
    break
  else:
    light=copy[:]
print(*light)

### FIXED CODE ###

N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    l=max(0,i-light[i])
    r=min(N-1,i+light[i])+1
    imo[l]+=1
    imo[r]-=1
  for i in range(1,N):
    imo[i]+=imo[i-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
  	s.append(input())
    
counts = [Counter(i) for i in s]
result = 0
for i in range(len(counts)):
  for j in range(i+1, len(counts), 1):
    if counts[i] == counts[j]:
      result += 1
print(result)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
  	s.append(input())

s = ["".join(sorted(i)) for i in s]
table = {}

count = 0
for word in s:
  if word in table:
    count += table[word]
    table[word] += 1
  else :
    table[word] = 1
print(count)
### BUGGY CODE ###

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
dp = [[0 for i in range(S)] for j in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(S):
    if A[i-1] <= j:
      dp[i][j] = dp[i-1][j-A[i-1]] + (dp[i-1][j]*2)
    else:
      dp[i][j] = dp[i-1][j]*2
bad_r = sum(dp[N][math.ceil(S/2):S])+1

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)
### BUGGY CODE ###

def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  dp = [[j for j in range(n+1)] for i in range(len(ab)+1)]
  if len(ab) == 0:
    return n
  if len(ab) == 1:
    a0, b0 = ab[0]
    return (n//a0)*b0 + n%a0
  if len(ab) == 2:
    a0, b0 = ab[0]; a1, b1 = ab[1]
    if a0 < a1: a0, b0, a1, b1 = a1, b1, a0, b0
    t = n // a0
    return max(((n-a0*i)//a1)*b1 + (n-a0*i)%a1 + i*b0 for i in range(t+1))
  else:
    dp = [j for j in range(n+1)]
    for ai, bi in ab:
      for j in range(ai, n+1):
        dp[j] = max(dp[j], dp[j-ai]+bi)
    return dp[-1]

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

N = solve(N, A, B)
N = solve(N, B, A)
print(N)

### FIXED CODE ###

def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  if len(ab) == 0:
    return n
  elif len(ab) == 1:
    a0, b0 = ab[0]
    return (n//a0)*b0 + n%a0
  elif len(ab) == 2:
    (a0, b0), (a1, b1) = ab
    if b0/a0 < b1/a1:
      a0, b0, a1, b1 = a1, b1, a0, b0
    return max(((n-a1*i)//a0)*b0 + (n-a1*i)%a0 + i*b1 for i in range(a0))
  else:
    dp = [j for j in range(n+1)]
    for ai, bi in ab:
      for j in range(ai, n+1):
        dp[j] = max(dp[j], dp[j-ai]+bi)
    return dp[-1]

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

N = solve(N, A, B)
N = solve(N, B, A)
print(N)
### BUGGY CODE ###

def combi(n):
    return n*(n-1)//2

def D159_1():
    N = int(input())
    A = input().split()
    tmp = 0
    idx = list(set(A))
    value = [ A.count(_) for _ in idx ]
    for n in value:
        tmp += combi(n)
    #sum = 0
    for i in A:
        j = idx.index(i)
        #sum += tmp - combi(j) + combi(j-1)
        print(int(tmp - combi(value[j]) + combi(value[j]-1)))


if __name__ == "__main__":
    D159_1()

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
import collections
A_count = collections.Counter(A)
 
import math
sum_ = 0
for ai in A_count:
    sum_ += (A_count[ai] * (A_count[ai] - 1)) // 2
 
for ai in A:
    #print(sum_ - (A_count[ai] * (A_count[ai] - 1)) // 2 + (A_count[ai] - 1) * (A_count[ai] - 2)) // 2
    l = A_count[ai] * (A_count[ai] - 1) // 2
    m = (A_count[ai] - 1) * (A_count[ai] - 2) // 2
    print(sum_ - l + m)
### BUGGY CODE ###

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

M = [[[0, 0] for i in range(W)] for j in range(H)]
V = [[[False, False] for i in range(W)] for j in range(H)]

def search(grid, w, h, direction):
    cnt = 0

    if direction == 'W':
        for _ in range(W):
            if w + cnt + 1 == W:
                break
            elif grid[h][w + cnt + 1] == '#':
                break

            cnt += 1

    if direction == 'H':
        for _ in range(H):
            if h + cnt + 1 == H:
                break
            elif grid[h + cnt + 1][w] == '#':
                break

            cnt += 1

    return cnt


for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            continue
        else:
            if not V[h][w][1]:
                cnt = search(grid, w, h, 'W')

                for i in range(cnt + 1):
                    V[h][w + i][1] = True
                    M[h][w + i][1] = cnt

for w in range(W):
    for h in range(H):
        if grid[h][w] == '#':
            continue
        else:
            if not V[h][w][0]:
                cnt = search(grid, w, h, 'H')

                for i in range(cnt + 1):
                    V[h + i][w][0] = True
                    M[h + i][w][0] = cnt

m = -1
for h in range(H):
    for w in range(W):
        if M[h][w][0] + M[h][w][1] > m:
            m = M[h][w][0] + M[h][w][1] + 1

print(m)


### FIXED CODE ###

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

grid = []

for i in range(H):
    s = input()
    r = []
    for j, x in enumerate(s):
        r.append(x)

    grid.append(r)


H_cnt = [[0] * W for _ in range(H)]
W_cnt = [[0] * W for _ in range(H)]

for r in range(H):
    idx = 0

    while idx < W:
        if grid[r][idx] == '.' and (idx == 0 or grid[r][idx - 1] == '#'):
            cnt = 1
            st = idx
            if idx == W - 1 or grid[r][idx + 1] == '#':
                W_cnt[r][idx] = 1
        elif grid[r][idx] == '.' and (idx == W - 1 or grid[r][idx + 1] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                W_cnt[r][i] = cnt
        elif grid[r][idx] == '.':
            cnt += 1
        elif grid[r][idx] == '#':
            pass

        idx += 1

for c in range(W):
    idx = 0

    while idx < H:
        if grid[idx][c] == '.' and (idx == 0 or grid[idx - 1][c] == '#'):
            cnt = 1
            st = idx
            if idx == H - 1 or grid[idx + 1][c] == '#':
                H_cnt[idx][c] = 1
        elif grid[idx][c] == '.' and (idx == H - 1 or grid[idx + 1][c] == '#'):
            cnt += 1
            for i in range(st, idx + 1):
                H_cnt[i][c] = cnt
        elif grid[idx][c] == '.':
            cnt += 1
        elif grid[idx][c] == '#':
            pass

        idx += 1

max_ = 0
for r in range(H):
    for c in range(W):
        max_ = max(max_, W_cnt[r][c] + H_cnt[r][c] - 1)

print(max_)
### BUGGY CODE ###

from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    color[X][Y]="gray"
                    queue.append([X,Y])

        for i in range(max(0,x-3),min(h,x+3)):
            for j in range(max(0,y-3),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black":
                        D[X][Y]=min(D[X][Y],D[x][y]+1)
                        color[X][Y]="gray"
                        queue.append([X,Y])
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)
### BUGGY CODE ###

II = lambda: int(input())
SI = lambda: input()
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
n,k = MI()
a = LI()
d = [-1]*n
d[0] = 0
for i in range(n):
	for j in range(i,min(i+k+1,n)):
		if d[j] == -1:
			d[j] = d[i]+abs(a[i]-a[j])
		else:
			d[j] = min(d[j],d[i]+abs(a[i]-a[j]))
print(d[-1])

### FIXED CODE ###

II = lambda: int(input())
SI = lambda: input()
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
n,k = MI()
a = LI()
d = [-1]*n
d[0] = 0
for i in range(n):
	for j in range(i,min(i+k+1,n)):
		if d[j] == -1:
			d[j] = d[i]+abs(a[i]-a[j])
		else:
			d[j] = min(d[j],d[i]+abs(a[i]-a[j]))
print(d[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

def rec(i):
    if dp[i] != 0:
        return dp[i]
    res = 0
    if i == 1 or i == 2:
        res = abs(H[i]-H[0])
        dp[i] = res
        return res
    elif i == 0:
        return 0
    else:
        res = abs(H[i]-H[i-2])+rec(i-2)
        res = min(res,abs(H[i]-H[i-1])+rec(i-1))
        dp[i] = res
        return res

rec(n-1)

print(dp[n-1]) 

### FIXED CODE ###

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

for i in range(1,n):
    if i == 1 or i == 2:
        dp[i] = abs(H[i]-H[0])
    else:
        dp[i] = min(abs(H[i]-H[i-2])+dp[i-2],abs(H[i]-H[i-1])+dp[i-1])

print(dp[n-1])
### BUGGY CODE ###

N, W, H = [int(x) for x in input().split()]

map_x = [False] * W
count_x = 0
map_y = [False] * H
count_y = 0

wifi = []
for _ in range(N):
    w = [int(x) for x in input().split()]
    wifi.append(w)


def check_x(l):
    for x, _, r in wifi:
        if x - r <= l < x + r:
            return True

    return False


def check_y(l):
    for _, y, r in wifi:
        if y - r <= l < y + r:
            return True

    return False


ans_x = True
for x in range(W):
    if not check_x(x):
        ans_x = False
        break

if not ans_x:
    for y in range(H):
        if not check_y(y):
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

N, W, H = [int(x) for x in input().split()]

map_x = [0] * W
map_y = [0] * H

for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    mx = max(0, x - w)
    map_x[mx] = max(map_x[mx], x + w - mx)
    my = max(0, y - w)
    map_y[my] = max(map_y[my], y + w - my)


def check_wifi(wifi):
    m = 0
    end = len(wifi)

    for i, x in enumerate(wifi):
        if x and i + x > m:
            m = i + x

        if m >= end:
            return True

        if i < m:
            continue

        return False

    return False


print('Yes' if check_wifi(map_x) or check_wifi(map_y) else 'No')
### BUGGY CODE ###

n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = {s}
flag = 0
while time < 3*n:
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  if time % 3 == 0:
    if t in now:
      flag = 1
      break
if flag == 1:
  print(time//3)
else:
  print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  #print(time,cnt,now)
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)
### BUGGY CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1,0), (0,1)]
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.append((y, x, 0))
    max_depth = 0
    while q:
        y, x, depth = q.popleft()
        visited[y][x] = 1
        max_depth = max(max_depth, depth)
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and visited[ny][nx] == 0:
                q.append((ny, nx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = deque()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H+2):
        for x in range(W+2):
            if S[y][x] == '.':
                d = bfs(y, x, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

def S(n):
    k=list(str(n))
    import functools
    return functools.reduce(lambda x,y:x+y,[int(i) for i in k])
k=int(input())
def T(n):
    return n/S(n)
i=10
A=[1,2,3,4,5,6,7,8,9]
while len(A)<k:
   t=1
   i_list=list(str(i))
   i_len=len(i_list)
   import functools
   I=functools.reduce(lambda x,y:x+y,[int(k) for k in i_list])
   for j in range(len(i_list)):
       if (10**(i_len-1-j))*I<i:
           if int(i_list[j])!=9:
               t=0
   if t==1:
       A.append(i)
   i+=1
for i in range(k):
    print(A[i])


### FIXED CODE ###

def S(n):
    k=list(str(n))
    import functools
    return functools.reduce(lambda x,y:x+y,[int(i) for i in k])
k=int(input())
def T(n):
    return n/S(n)
def f(N):
    len_N=len(str(N))
    A=[10**len_N+10**i-1 for i in range(len_N)]
    B=[T(i) for i in A]
    ans1=A[B.index(min(B))]
    i=0
    while True:
        I=10**(len_N-1)+10**i-1
        J=10**(len_N-1)+10**(i+1)-1
        if T(J)<T(I):
            i+=1
        else:
            break
    C=[((N+1)//(10**i))*10**i+j*10**i-1 for j in range(1,11)]
    D=[T(i) for i in C]
    ans2=C[D.index(min(D))]
    if T(ans1)<T(ans2):
        return(ans1)
    else:
        return(ans2)
K=[]
N=1
while len(K)<k:
    K.append(N)
    N=f(N)
for i in range(k):
    print(K[i])
### BUGGY CODE ###

# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))

ans=[]
ha1=[]
ha = [k for i in range(e2) for k in range(1,e1+1) if h[i][0]<=k<=h[i][1]]
sha=sorted(ha)

ma=0

count=1
#最大値求める
for i in range(len(sha)-1):
    if sha[i]==sha[i+1]:
        count+=1
    else:
        if count>=e2:
            ha1.append(count)
        count=1

if count>=e2:
    ha1.append(count)
print(len(ha1))



# for i in range(1,e1+1):
#     count=0
#     for k in range(e2):
#         if h[k][0]<=i<=h[k][1]:
#             count+=1
#     if count==e2:
#         ans.append(count)

# print(len(ans))
    




### FIXED CODE ###

# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))
L=[]
R=[]
for i in range(len(h)):
    L.append(h[i][0])
for i in range(len(h)):
    R.append(h[i][1])

if min(R)>=max(L):
    print(min(R)-max(L)+1)
else:
    print(0)
### BUGGY CODE ###

def warshall(N, ABCs):
    dists = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


from itertools import permutations


def solve(N, M, R, Rs, ABCs):
    dists = warshall(N, ABCs)
    ans = 10 ** 10
    for way in permutations(Rs):
        ans = min(ans, sum([dists[i - 1][j - 1] for i, j in zip(way, way[1:])]))

    return ans

if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))


### FIXED CODE ###

from itertools import permutations
import heapq

INF = 100000 * 200 * 10

def warshall(N, ABCs):
    dists = [[INF for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


def dijkstra(s, e, N, ABCs):
    adjlist = [[] for _ in range(N)]
    for a, b, c in ABCs:
        adjlist[a - 1].append((b, c))
        adjlist[b - 1].append((a, c))

    q = [(0, s)]
    while len(q):
        d, i = heapq.heappop(q)
        if i == e:
            return d
        for nexti, nextd in adjlist[i - 1]:
            heapq.heappush(q, (d + nextd, nexti))
    return None


def dense_dijkstra(s, e, N, ABCs):
    distsmap = [[-1 for _ in range(N)] for __ in range(N)]
    for a, b, c in ABCs:
        distsmap[a - 1][b - 1] = c
        distsmap[b - 1][a - 1] = c

    dists = [INF for _ in range(N)]
    visited = [False for _ in range(N)]
    dists[s - 1] = 0

    while True:
        minW, index = min([(dists[i], i) for i in range(N) if not visited[i]])
        visited[index] = True
        if minW == INF:
            return -1
        if index + 1 == e:
            return minW
        for rindex, w in enumerate(distsmap[index]):
            if w == -1:
                continue
            dists[rindex] = min(dists[rindex], minW + w)


def solve(N, M, R, Rs, ABCs):
    dists = [[-1 for _ in range(N)] for __ in range(N)]
    ans = INF
    for way in permutations(Rs):
        tans = 0
        for s, e in zip(way, way[1:]):
            if dists[s - 1][e - 1] == -1:
                d = dense_dijkstra(s, e, N, ABCs)
                dists[s - 1][e - 1] = d
                dists[e - 1][s - 1] = d
            else:
                d = dists[s - 1][e - 1]
            tans += d
        ans = min(ans, tans)

    return ans

if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))
### BUGGY CODE ###

#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**18
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
#solve
n,m,s,t=map(int,input().split())
s-=1
t-=1
yen_edge=[[]for _ in range(n)]
snuuk_edge=[[]for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  yen_edge[u].append([v,a])
  yen_edge[v].append([u,a])
  snuuk_edge[u].append([v,b])
  snuuk_edge[v].append([u,b])
yen=dijkstra(s,n,yen_edge)
snuuk=dijkstra(t,n,snuuk_edge)
ans=[10**15-(yen[i]+snuuk[i])for i in range(n)]
for i in range(n-2,-1,-1):ans[i]=max(ans[i],ans[i+1])
for i in ans:print(i)


### FIXED CODE ###

#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**16
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
#solve
n,m,s,t=map(int,input().split())
s-=1
t-=1
yen_edge=[[]for _ in range(n)]
snuuk_edge=[[]for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  yen_edge[u].append([v,a])
  yen_edge[v].append([u,a])
  snuuk_edge[u].append([v,b])
  snuuk_edge[v].append([u,b])
yen=dijkstra(s,n,yen_edge)
snuuk=dijkstra(t,n,snuuk_edge)
ans=[10**15-(yen[i]+snuuk[i])for i in range(n)]
for i in range(n-2,-1,-1):ans[i]=max(ans[i],ans[i+1])
for i in ans:print(i)