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

n=int(input())
l=list(map(int,input().split()))
l.sort()
c=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k]:
        c+=1
print(c)    

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
c=0
for i in range(n-2):
  for j in range(i+1,n-1):
    u=l[i]-l[j]
    if l[j+1]<=u:
      break
    ok=j+1
    ng=n
    while ng-ok>1:
      center=(ok+ng)//2
      if l[center]>u:
        ok=center
      else:
        ng=center
    c+=ng-j-1
print(c)
### BUGGY CODE ###

import sys
import math
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = np.array(rl())
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = np.array([limit // i for i in range(1, N)])
Z = X * Y
answer = Z.sum()%MOD
print(answer)


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
C.sort(reverse=True)
C=C[:K]

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]

E=sorted([d+c for d,c in product(D,C)],reverse=True)
for i in range(K):
    print(E[i])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
C=C[:K]

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]
E=sorted([d+c for d,c in product(D,C)],reverse=True)
E=E[:K]
for i in range(K):
    print(E[i])
### BUGGY CODE ###

n,k=map(int,input().split())
exp=tuple(map(lambda x: (int(x)+1)/2,input().split()))
ans=0
for i in range(0,n-k+1):
  ans=max(ans,sum(exp[i:i+k]))
print(ans)

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
exp=tuple(map(lambda x: (int(x)+1)/2,input().split()))
l=np.cumsum(exp)

ans=l[k-1]
for i in range(0,n-k):
  x=l[i+k]-l[i]
  ans=max(ans,x)
print(ans)
### BUGGY CODE ###

n= int(input().strip())
a= list(map(int, input().strip().split()))
x=0
for i in range(n-1):
    for j in range(i+1,n):
        x+=(a[i]*a[j])%(10**9+7)
        x=x%(10**9+7)
print(x)

### FIXED CODE ###

n= int(input().strip())
a= list(map(int, input().strip().split()))
x=0
A=0

for i in range(n):
    A+=a[i]
x=0
for i in range(n):
    x+=a[i]*(A-a[i])
x=x//2
x=x%(10**9+7)
print(x)
### BUGGY CODE ###

import numpy as np
N, K, Q = [int(x) for x in input().split()]

scores = np.full(N, K)
for i in range(Q):
    ans = int(input())
    scores -= 1
    scores[ans - 1] += 1

for score in scores:
    print('Yes' if score > 0 else 'No')
    

### FIXED CODE ###

N, K, Q = [int(x) for x in input().split()]

scores = [K - Q] * N
for i in range(Q):
    ans = int(input())
    scores[ans - 1] += 1
    

for score in scores:
    print('Yes' if score > 0 else 'No')
### BUGGY CODE ###

t = int(input())
  
def solve(n,a,b,c,d):
  sol = [n*d]
  if n>=2:
    if n%2 == 0:
      sol.append(a+solve(n//2,a,b,c,d))
    else:
      sol.append(a+d+solve((n+1)//2,a,b,c,d))
      sol.append(a+d+solve((n-1)//2,a,b,c,d))
  if n>=3:
    if n%3 == 0:
      sol.append(b+solve(n//3,a,b,c,d))
    else:
      bd = n%3
      sol.append(b+bd*d+solve((n-bd)//3,a,b,c,d))
      sol.append(b+(3-bd)*d+solve((n-bd+3)//3,a,b,c,d))
  if n>=5:
    if n%5 == 0:
      sol.append(c+solve(n//5,a,b,c,d))
    else:
      cd = n%5
      sol.append(c+cd*d+solve((n-cd)//5,a,b,c,d))
      sol.append(c+(5-cd)*d+solve((n-cd+5)//5,a,b,c,d))
  return min(sol)

for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))

### FIXED CODE ###

t = int(input())

def solve(n,a,b,c,d):
  mem = {0:0,1:d}
  def f(n):
    if n in mem:
      return mem[n]
    ret = n*d
    if n%2 == 0:
      ret = min(ret,a+f(n//2))
    else:
      ret = min(ret,a+d+f(n//2+1),a+d+f(n//2))
    
    if n%3 == 0:
      ret = min(ret,b+f(n//3))
    elif n%3 == 1:
      ret = min(ret,b+d+f(n//3))
    else:
      ret = min(ret,b+d+f(n//3+1))
    
    if n%5 == 0:
      ret = min(ret,c+f(n//5))
    elif n%5 == 1:
      ret = min(ret,c+d+f(n//5))
    elif n%5 == 2:
      ret = min(ret,c+d+d+f(n//5))
    elif n%5 == 3:
      ret = min(ret,c+d+d+f(n//5+1))
    else:
      ret = min(ret,c+d+f(n//5+1))
    mem[n] = ret
    return ret
  return f(n)
 
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))
### BUGGY CODE ###

NUM = [10000, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))

dp = ["x"] * (n + 1)
dp[0] = ""
for i in range(1, n + 1):
    for a in aa:
        if i - NUM[a] >= 0 and dp[i - NUM[a]] != "x":
            tmp = dp[i - NUM[a]] + str(a)
            tmp = "".join(sorted(tmp, reverse=True))
            if int(tmp) > (0 if dp[i] == "x" else int(dp[i])):
                dp[i] = tmp
print(dp[n])

### FIXED CODE ###

from copy import deepcopy
NUM = [10000, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))

dp = [[-1 for j in range(9)] for i in range(n + 1)]
for j in range(9):
    dp[0][j] = 0
for i in range(1, n + 1):
    for a in aa:
        if i - NUM[a] >= 0 and dp[i - NUM[a]][0] != -1:
            tmp = deepcopy(dp[i - NUM[a]])
            tmp[9 - a] += 1
            if sum(tmp) > sum(dp[i]) or (sum(tmp) == sum(dp[i]) and tmp > dp[i]):
                dp[i] = tmp
ans = ""
for j in range(9):
    for k in range(dp[n][j]):
        ans += str(9 - j)
print(ans)
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
b=[0]*(10**5+2)
if a[0]==a[-1]:
  print(n)
else:
  for i in range(a[-1]+1):
    b[i]=a.count(i)
  for i in range(a[-1]-1):
    ans=max(ans,b[i]+b[i+1]+b[i+2])
  print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=collections.Counter(a)
ans=1
for i in range(min(a),max(a)+1):
  goukei=c[i-1]+c[i]+c[i+1]
  ans=max(ans,goukei)
print(ans)
### BUGGY CODE ###

n=int(input())
for i in range(1,n+1):
    cnt=0
    for x in range(1,10**2+1):
        for y in range(1,10**2+1):
            for z in range(1,10**2+1):
                if x**2+y**2+z**2+x*y+y*z+z*x==i:cnt+=1
                elif x**2+y**2+z**2+x*y+y*z+z*x>i:break
    print(cnt)

### FIXED CODE ###

import collections

l=[]
n=int(input())
for x in range(1,10**2+1):
    if x**2>n:continue
    for y in range(1,10**2+1):
        if x**2+y**2>n:continue
        for z in range(1,10**2+1):
            if x**2+y**2+z**2>n:continue
            l.append(x**2+y**2+z**2+x*y+y*z+z*x)

c=collections.Counter(l)
for x in range(1,n+1):
    print(c[x])
### BUGGY CODE ###

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

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

L=[[]for i in range(N+1)]
D=dict()
for i in range(M):
    l,r,d=map(int,input().split())
    L[l].append([r,d])
    L[r].append([l,-d])
    D[i]=(l,r,d)
    
C=["N" for i in range(N+1)]

def dfs(x):
    for i,j in L[x]:
        if C[i]=="N":
            C[i]=C[x]+j
            dfs(i)

for i in range(1,N+1):
    if C[i]=="N":
        C[i]=0
        dfs(i)
#print(C)
#print(D)
for i in range(M):
    l,r,d=D[i]
    if C[r]-C[l]!=d:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

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

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

L=[[]for i in range(N+1)]
D=dict()
for i in range(M):
    l,r,d=map(int,input().split())
    L[l].append([r,d])
    L[r].append([l,-d])
    D[i]=(l,r,d)
    
C=["N" for i in range(N+1)]

def dfs(x):
    for i,j in L[x]:
        if C[i]=="N":
            C[i]=C[x]+j
            dfs(i)

for i in range(1,N+1):
    if C[i]=="N":
        C[i]=0
        dfs(i)
#print(C)
#print(D)
for i in range(M):
    l,r,d=D[i]
    if C[r]-C[l]!=d:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

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

def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    pre = -1
    for i in range(num)[::-1]:
        if data[i] == pre:
            data.pop(i)
        pre = data[i]

    num = len(data)

    dic = defaultdict(int)
    mod = 10 ** 9 + 7
    dp = [1 for i in range(num + 1)]

    for i in range(num):
        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict

def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    dic = defaultdict(int)
    mod = 10 ** 9 + 7
    dp = [1 for i in range(num + 1)]

    for i in range(num):
        if i != 0:
            if data[i] == data[i - 1]:
                dp[i + 1] = dp[i]
                continue

        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

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

s = input()

ans = 0
stack = [s[0]]
flg = False
for i in range(1,len(s)):
        if len(stack) > 0:
            if stack[0] != s[i]:
                ans += 2
                stack.pop(0)
            else:
                stack.insert(0, s[i])
        else:
            stack.insert(0, s[i])

print(ans)


### FIXED CODE ###

s = list(input())
count_zero = 0
count_one = 0
for i in range(len(s)):
    if s[i] == '1':
        count_one += 1
    else:
        count_zero += 1

print(len(s) - abs(count_zero - count_one))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

def plus_and_check(list):
    sum_up = 0
    for i in range(len(list)-1):
        sum_up += list[i]
    i = 0
    while i < 8:
        number_1 = 10 * i
        number_2 = 10 * (i+1)
        if number_2  > sum_up and number_1 < sum_up:
            return i
        else:
            continue
        i = i + 1

l = map(int, raw_input().split())
print "%d" % plus_and_check(l)

### FIXED CODE ###

import sys

a = []
answer_array = []
for line in sys.stdin:
    a.append(map(int, line.strip().split()))
    #except StopIteration:
        #break

for i in range(len(a)):
    sum_up = a[i][0] + a[i][1]

    answer = len(str(sum_up))

    answer_array.append(answer)

for j in range(len(answer_array)):
    print answer_array[j]
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 0
for a in range(N):
    for b in range(a + 1, N):
        for c in range(b + 1, N):
            if L[a] < L[b] + L[c] and L[b] < L[a] + L[c] and L[c] < L[b] + L[a]:
                ans += 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-1, 1, -1):
    for j in range(i - 1, 0, -1):
        x = L[i] - L[j]
        bottom = bisect_right(L, x)
        if j > bottom:
            ans += j - bottom
print(ans)
### BUGGY CODE ###

# educational DP contest F

X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

# print(dp[x][y])

ans = ''
while x > 0 and y > 0:
    if dp[x][y] == dp[x][y - 1]:
        y -= 1
    elif dp[x][y] == dp[x - 1][y]:
        x -= 1
    else:
        ans += X[x - 1]
        x -= 1
        y -= 1

print(ans[::-1])


### FIXED CODE ###

# educational DP contest F

X = input()
Y = input()
x = len(X)
y = len(Y)

dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]
for i in range(x):
    for j in range(y):
        if X[i] == Y[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

# print(dp[x][y])

ans = ''
while x > 0 and y > 0:
    if dp[x][y] == dp[x][y - 1]:
        y -= 1
    elif dp[x][y] == dp[x - 1][y]:
        x -= 1
    else:
        ans += X[x - 1]
        x -= 1
        y -= 1

print(ans[::-1])
### BUGGY CODE ###

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

if any([abs(A[i+1] - A[i] == 1) for i in range(len(A)-1)]):
  print(0)
  exit()

mod = pow(10, 9) + 7
dp = [0] * (N+1+2)
dp[0] = 1
if 1 not in A:
  dp[1] = 1
  
for i in range(2, N+1):
  if i not in A:
    if i-1 not in A:
      dp[i] = (dp[i] + dp[i-1]) % mod
    if i-2 not in A:
      dp[i] = (dp[i] + dp[i-2]) % mod
print(dp[N])

### FIXED CODE ###

N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]
mod = pow(10,9) + 7

dp = [0]*(N+1)
dp[0] = 1

ok = [True]*(N+1)
for i in a:
  ok[i] = False

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= mod
      
print(dp[N])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    if s[i] == s[j]:
      continue
    for k in range(j+1,n):
      if k -j == j -i:
        continue
      if s[i] == s[k] or s[j] == s[k]:
        continue
      else:
        ans += 1
        
print(ans)
        

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count('R')*s.count('B')*s.count('G')
for i in range(n-2):
    for j in range(i+1,n-1):
        k = j + (j - i)
        if k>=n:break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1
        
print(ans)
### BUGGY CODE ###

import heapq

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

F = sorted(F, reverse = True)
A = sorted(A)
flg = 0
heap = []

for i in range(N):
	heapq.heappush(heap, [- A[i] * F[i], A[i], F[i]])
	
for i in range(K):
	score, tmp_A, tmp_F = heapq.heappop(heap)
	if tmp_A > 0:
		tmp_A -= 1
		heapq.heappush(heap, [- tmp_A * tmp_F, tmp_A, tmp_F])
	else:
		flg = 1
		break
		
if flg:
	print(0)
else:
	ret = heapq.heappop(heap)
	print(-1 * ret[0])	

### FIXED CODE ###

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

A.sort()
F.sort(reverse = True)

ng = -1
ok = 10 ** 12

while ok - ng > 1:
	mid = (ok + ng) // 2
	ctr = 0
	for i in range(N):
		ctr += max(0, A[i] - mid // F[i])
	if ctr <= K:
		ok = mid
	else:
		ng = mid

print(ok)
### BUGGY CODE ###

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

cnt, su, r = 0, 0, 0
for l in range(n):
    su = 0
    r = l
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
        cnt += 1
    if l == 0 and r == n:
        print(n * (n + 1) // 2)
        exit()
print(cnt)


### FIXED CODE ###

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

cnt, su, r = 0, 0, 0
for l in range(n):
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
    cnt += r - l
    if l == r:
        r += 1
    else:
        su -= a[l]
print(cnt)
### BUGGY CODE ###

from decimal import *

n = int(input())
ans = 0
vec = [Decimal(input()) for i in range(n)]
vec25 = [[0 for i in range(50)] for i in range(50)]  # 整数にするのに余っている2,5の数
for i in range(n):
    a = vec[i] * 1000000000
    num2 = -9
    num5 = -9
    while a%2 == 0:
        a //= 2
        num2 += 1
    while a%5 == 0:
        a //= 5
        num5 += 1
    vec25[num2][num5] += 1
for i in range(-9, 40): 
    for j in range(-9, 20):
        for k in range(max(-9, -i), 40):
            for l in range(max(-9, -j), 20):
                if i+k >= 0 and j+l >= 0 :
                    if i != k or j != l :
                        ans += vec25[i][j] * vec25[k][l]
                    else :
                        ans += vec25[i][j] * (vec25[i][j] - 1)
ans //= 2
print(ans)

### FIXED CODE ###

from decimal import *

n = int(input())
ans = 0
vec = [Decimal(input()) for i in range(n)]
vec25 = [[0 for i in range(50)] for i in range(50)]  # 整数にするのに余っている2,5の数
for i in range(n):
    a = int(vec[i] * 1000000000)
    num2 = -9
    num5 = -9
    while a%2 == 0:
        a //= 2
        num2 += 1
    while a%5 == 0:
        a //= 5
        num5 += 1
    vec25[num2][num5] += 1
for i in range(-9, 40): 
    for j in range(-9, 20):
        for k in range(max(-9, -i), 40):
            for l in range(max(-9, -j), 20):
                if i+k >= 0 and j+l >= 0 :
                    if i != k or j != l :
                        ans += vec25[i][j] * vec25[k][l]
                    else :
                        ans += vec25[i][j] * (vec25[i][j] - 1)
ans //= 2
print(ans)
### BUGGY CODE ###

k, s = list(map(int, input().split()))

ans = 0
for i in range(k+1):
    for j in range(k+1):
        for m in range(k+1):
            if ((i+j+m) == s):
                ans += 1

print(ans)


### FIXED CODE ###

k, s = list(map(int, input().split()))

ans = 0
for i in range(k+1):
    for j in range(k+1):
        m = s - i - j
        if (0 <= m <= k):
            ans += 1

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

import heapq
from collections import defaultdict
def gijkstra(n,E,key=1,s=1):
    d = [float('inf')]*(n+1)
    d[s] = 0
    hq = [(0,s)]
    while hq:
        u = heapq.heappop(hq)[1]
        for e in E[u]:
            c, v = d[u] + e[key], e[0]
            if d[v] > c:
                d[v] = c
                heapq.heappush(hq,(c,v))
    return d

n, m, s, t =  map(int,input().split())
E = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E[u].add((v,a,b))
    E[v].add((u,a,b))
d1 = gijkstra(n,E,key=1,s=s)
d2 = gijkstra(n,E,key=2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d = [min(d[0],d1[i]+d2[i])] + d
[print(10**15-c) for c in d]

### FIXED CODE ###

import heapq
from collections import defaultdict
def gijkstra(n,E,s=1):
    d = [float('inf')]*(n+1)
    p = [-1]*(n+1)
    hq = [(0,s)]
    d[s] = 0
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in E[u]:
            if d[v] > d[u] + c:
                d[v], p[v] = d[u]+c, u
                heapq.heappush(hq, (d[u]+c, v))
    return d, p

n, m, s, t =  map(int,input().split())
E1 = defaultdict(set)
E2 = defaultdict(set)

for i in range(m):
    u,v,a,b = tuple(map(int,input().split()))
    E1[u].add((v,a))
    E1[v].add((u,a))
    E2[u].add((v,b))
    E2[v].add((u,b))
d1, _ = gijkstra(n,E1,s=s)
d2, _ = gijkstra(n,E2,s=t)
d = [d1[-1] + d2[-1],]
for i in range(n-1,0,-1):
    d.append(min(d[-1],d1[i]+d2[i]))
[print(10**15-c) for c in reversed(d)]
### BUGGY CODE ###

#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
for i, j in itertools.product(range(H), range(W)):
    if Board[i][j] == '#':
        # Board[i][j] = 0
        q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)


### FIXED CODE ###

#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
# import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            # y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)
### BUGGY CODE ###

l, r = map(int,input().split())
arr = []
if r-l <= 2019**2:
  for i in range(l,r):
    for j in range(i+1,r+1):
      a = (i*j)%2019
      arr.append(a)
  print(min(arr))
else:
  print(0)

### FIXED CODE ###

l, r = map(int,input().split())
arr = []
if r-l < 2019**2:
  for i in range(l,r):
    for j in range(i+1,r+1):
      a = (i*j)%2019
      arr.append(a)
    if 0 in arr:
      break
  print(min(arr))
else:
  print(0)
### BUGGY CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
M=np.array(M)
c_list=[]
for i in range(1,N+1):
    c_list.append(np.count_nonzero(M == i))
for k in range(N):
    c_list[M[k]-1]-=1
    l=np.array(list(filter((lambda x: x >=2),c_list)))
    ans=sum(l*(l-1))//2
    print(ans)
    c_list[M[k] - 1] += 1

### FIXED CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
num_list=np.array([0]*(2*10**5+1))
ans=0
for i in M:
    num_list[i-1]+=1
ans=sum(num_list*(num_list-1))//2
for k in range(N):
    num=num_list[M[k]-1]-1
    print(ans-num)