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

import sys
input = sys.stdin.buffer.readline

def main():
    n, m, k = map(int, input().split())
    parent_f = list(range(n+1))
    rank_f = [0]*(n+1)
    parent_b = list(range(n+1))
    rank_b = [0]*(n+1)
    group_f = [set() for _ in range(n+1)]
    group_b = [set() for _ in range(n+1)]
    group_index_f = [None]*(n+1)
    group_index_b = [None]*(n+1)
    friends = [set() for i in range(n+1)]
    blocks = [set() for i in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        unite(a, b, parent_f, rank_f)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
        unite(c, d, parent_b, rank_b)
    for i in range(1, n+1):
        rf = root(i, parent_f)
        rb = root(i, parent_b)
        group_f[rf] |= {i}
        group_b[rb] |= {i}
        group_index_f[i] = rf
        group_index_b[i] = rb
    for i in range(1, n+1):
        print(len(group_f[group_index_f[i]]-friends[i]-blocks[i]-{i}))
    

def root(x, parent):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x], parent)
    return parent[x]

def unite(x, y, parent, rank):
    x = root(x, parent)
    y = root(y, parent)
    if x != y:
        if rank[x] > rank[y]:
            parent[y] = x
        elif rank[x] < rank[y]:
            parent[x] = y
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

class UnionFind:
    __slots__ = ["data"]
    
    def __init__(self, n=0):
        self.data = [-1]*(n+1)
    
    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.data[x] < self.data[y]:
                self.data[x] += self.data[y]
                self.data[y] = x
            else:
                self.data[y] += self.data[x]
                self.data[x] = y
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.data[self.root(x)]
                


def main():
    n, m, k = map(int, input().split())
    friends = [set() for _ in range(n+1)]
    blocks = [set() for _ in range(n+1)]
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        uf.unite(a, b)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
    for i in range(1, n+1):
        nf = len(friends[i])
        nb = sum([uf.same(i, b) for b in blocks[i]])
        ans = uf.size(i) - 1 - nf - nb
        print(ans)


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import atan, tan, pi

a, b, x = map(int, readline().split())


def max_v(si):
    si = si / 180 * pi
    if si < atan(b / a):
        area = a * b - a ** 2 * tan(si) / 2
    else:
        area = b * (b / tan(si) / 2)
    return area * a


low = 0
high = 90
while high - low > 1e-7:
    mid = (low + high) // 2
    if max_v(mid) <= x:
        high = mid
    else:
        low = mid
print((high + low) / 2)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import atan, tan, pi

a, b, x = map(int, readline().split())


def max_v(si):
    si = si / 180 * pi
    if si < atan(b / a):
        area = a * b - a ** 2 * tan(si) / 2
    else:
        area = b * (b / tan(si) / 2)
    return area * a


low = 0
high = 90
while high - low > 1e-7:
    mid = (low + high) / 2
    if max_v(mid) <= x:
        high = mid
    else:
        low = mid
print((high + low) / 2)
### BUGGY CODE ###

n = int(input())
state = [n, 0, 0, 0, 0, 0]
capacities = list(reversed([int(input()) for _ in range(5)]))
t = 0
while state[5]!=n:
    for idx, capa in enumerate(capacities):
        passengers = capa if capa <= state[4-idx] else state[4-idx]
        if passengers != 0:
            state[4-idx] -= passengers
            state[5-idx] += passengers
    t += 1
print(t)


### FIXED CODE ###

import math
n = int(input())
state = [n, 0, 0, 0, 0, 0]
capacities = [int(input()) for _ in range(5)]
for i in range(1, 5):
    if capacities[i - 1] < capacities[i]:
        capacities[i] = capacities[i - 1]
print(4+math.ceil(n/capacities[4]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
l_array = []
r_array = []
for i, X in enumerate(A):
    l_array.append(i + X)
    r_array.append(i - X)

for x in l_array:
    count += r_array.count(x)
print(count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = 0
l_array = []
r_array = []
for i, X in enumerate(A):
    l_array.append(i + X)
    r_array.append(i - X)

counter = Counter(r_array)

for x in l_array:
    count += counter.get(x, 0)
print(count)
### BUGGY CODE ###

S = input().strip()
Sb = [c == "B" for c in S]

def reverse(Sb,i):
    _list = Sb.copy()
    _list[i] = not _list[i]
    return _list

def operate_onestep(Sb):
    _list = Sb.copy()
    cnt = 0
    flg = True
    while flg:
        flg = False
        for i in range(len(_list)-1):
            if _list[i] and not _list[i+1]:
                cnt += 1
                _list = reverse(_list,i)
                _list = reverse(_list,i+1)
                flg = True
    return cnt

print(operate_onestep(Sb))

### FIXED CODE ###

S = input().strip()

w_total = 0
num_op = 0
for i,c in enumerate(S):
    if c == "W":
        w_total += 1
        num_op += i + 1 - w_total
        
print(num_op)
### BUGGY CODE ###

n = int(input())
p = list(int(x) for x in input().split())
sum = 1

for i in range(1, n):
    if(all(p[i] < j for j in p[:i])):
        sum += 1

print(sum)

### FIXED CODE ###

import numpy as np

n = int(input())
p = np.array(list(int(x) for x in input().split()))
sum = 0
low = p[0] + 1

for i in p:
    if(i < low):
        sum += 1
        low = i

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

import itertools

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_3(a,b,c):
    p = gcd(a,b)
    q = gcd(p,c)
    return q

k = int(input())
ans = 0

num = list(itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)))

for l in num:
    a,b,c = l
    ans += gcd_3(a,b,c)
print(ans)

### FIXED CODE ###

import itertools

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_3(a,b,c):
    a = gcd(gcd(a,b),c)
    return a

k = int(input())
ans = 0

num = list(itertools.combinations_with_replacement(range(1,k+1),3))

for l in num:
    a,b,c = l
    if a==b==c:
        ans += a
    elif a!=b!=c:
        ans += gcd_3(a,b,c)*6
    else:
        ans += gcd_3(a,b,c)*3
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [0] * (N ** 2)
tablelr = [0] * (N ** 2)
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i * N + j] = min(abs(a[j][0] - x), min(abs(a[j][0]), abs(a[j][1]))) * a[j][2]
    tablelr[i * N + j] = min(abs(a[j][1] - y), min(abs(a[j][0]), abs(a[j][1]))) * a[j][2]
tableudi = [10 ** 20 for _ in range((1 << N) * N)]
tablelri = [10 ** 20 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], tableud[j * N + k])
        tablelri[i * N + k] = min(tablelri[i * N + k], tablelr[j * N + k])
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 20] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    #print(t, res, rres)
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)



### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
table = [0] * N
for k in range(N): table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
        lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
        tableudi[i * N + k] = min(tableudi[i * N + k], ud)
        tablelri[i * N + k] = min(tablelri[i * N + k], lr)
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    #print(t, res, rres)
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)
### BUGGY CODE ###

from collections import defaultdict
from math import factorial

mem = {}


def num_combinations(_n, r):
    if _n < r:
        return 0
    elif _n in mem.keys():
        return mem[_n]
    mem[_n] = int(factorial(_n) / (factorial(r) * factorial(_n - r)))
    return mem[_n]


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)

    for n in xs:
        freq[n] += 1

    res = 0

    for k in range(len(xs)):
        res = 0
        for num in freq.keys():
            res += num_combinations(freq[num] - (1 if xs[k] == num else 0), 2)
        print(res)


### FIXED CODE ###

from collections import defaultdict


def num_combinations(_n):
    return _n * (_n - 1) // 2


if __name__ == '__main__':
    n = int(input())
    xs = [int(s) for s in input().split()]
    freq = defaultdict(int)

    for n in xs:
        freq[n] += 1

    total = sum([num_combinations(n) for n in freq.values()])
    for x in xs:
        print(total - (freq[x] - 1))
### BUGGY CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def inv(a):
    return pow(a, mod - 2, mod)


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)

    res = 0
    for k in range(K + 1):
        res += M * pow(M - 1, N - 1 - k, mod) * C(F, N - 1, k) % mod
        res %= mod

    print(res % mod)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def functional(N):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F

D = {}
def inv(a):
    if a in D:
        return D[a]
    
    d = pow(a, mod - 2, mod)
    D[a] = d
    return d


def C(F, a, b):
    return F[a] * inv(F[a - b]) * inv(F[b]) % mod 


def main():
    N, M, K = read_values()
    F = functional(N)
 
    res = 0
    for k in range(K + 1):
        res += M * pow(M - 1, N - 1 - k, mod) * C(F, N - 1, k) % mod
        res %= mod
 
    print(res % mod)


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

N = int(input())
A = list(map(int,input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

for i in range(2,N):
  a = A[i]
  ma = (i+2)//2
  mi = i//2
  dp[i+1][ma] = max(dp[i][ma],dp[i-1][ma-1]+a)
  dp[i+1][mi] = max(dp[i][mi],dp[i-1][mi-1]+a)

print(dp[-1][N//2])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
INF = -float('inf')
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=INF,INF,INF,INF,INF
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])
dp[1][0],dp[2][0]=0,0

for i in range(2,N):
  a = A[i]
  ma = (i+2)//2
  mi = i//2
  dp[i+1][ma] = max(dp[i][ma],dp[i-1][ma-1]+a)
  dp[i+1][mi] = max(dp[i][mi],dp[i-1][mi-1]+a)

print(dp[-1][N//2])
### BUGGY CODE ###

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

from math import floor

def bubble(x):
	for i in range(len(x)-1):
		if x[i] < x[i+1]:
			x[i], x[i+1] = x[i+1], x[i]
		else:
			break

	return x

a.sort(reverse=True)

for _ in range(m):
	a[0] /= 2
	a = bubble(a)

ans = 0
for ele in a:
	ans += floor(ele)

print(ans)

### FIXED CODE ###

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

from math import floor
import heapq

for i in range(n):
	a[i] = -a[i]

h = []
for ele in a:
	heapq.heappush(h, ele)

for _ in range(m):
	mx = heapq.heappop(h)
	mx /= 2
	heapq.heappush(h, mx)

ans = 0
for ele in h:
	ans += floor(-ele)

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

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

t=0
v=2*n//k

for apb in range(k,k*(v+1),k):
  for bpc in range(k,k*(v+1),k):
    for cpa in range(k,apb+bpc,k):
      if (apb+bpc+cpa)%2:
        continue
      a = (apb+bpc+cpa - 2*bpc)//2
      b = (apb+bpc+cpa - 2*cpa)//2
      c = (apb+bpc+cpa - 2*apb)//2
      if 0 < a and a <= n and 0 < b and b<=n and 0 < c and c <= n:
        t += 1

print(t)



### FIXED CODE ###

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

x = n//k
y = x if k%2 else n//(k//2)

print(x**3+(y-x)**3)
### BUGGY CODE ###

def comb(n, r):
    bunshi = 1
    for i in range(n-r+1,n+1):
        bunshi = bunshi*i
    bunbo = 1
    for i in range(1,r+1):
        bunbo = bunbo * i 
    return bunshi//bunbo

def pascal(n):
    c = [[0 for i in range(n+1)] for j in range(n+1)]
    c[0][0] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j == 0 or j == i:
                c[i][j] = 1
                continue
            c[i][j] = c[i-1][j-1] +c[i-1][j]
    return(c)

def pascal2(n):
    c = [[0 for i in range(2)] for j in range(n)]
    c[0][0] = 2
    c[0][1] = 1
    for i in range(1, n+1):
        for j in range(n+1):
            if j == 0 or j == i:
                c[i][j] = 1
                continue
            c[i][j] = c[i-1][j-1] +c[i-1][j]
    return(c)

N = int(input())
A = list(map(int, input().split()))
c = pascal(N)
duplication = {}
ans = 0
for x in A:
    if x in duplication:
        continue
    count = A.count(x)
    if count > 0:
        duplication[x] = count
        # ans += comb(count,2)
        ans += c[count][2]
for x in A:
    if x not in duplication:
        print(ans)
    else:
        # print(ans -comb(duplication[x],2) +comb(duplication[x]-1,2))
        print(ans -duplication[x]+1)
        # print(ans -c[duplication[x]][2] +c[duplication[x]-1][2])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# TLE
def test():
    duplication = {}
    ans = 0
    for x in A:
        if x in duplication:
            continue
        count = A.count(x)
        if count > 1:
            duplication[x] = count
            ans += count*(count-1)//2
    for x in A:
        if x not in duplication:
            print(ans)
        else:
            print(ans -(duplication[x]-1))
from collections import defaultdict

sum = 0
count_dic = defaultdict(int)
for x in A:
    count_dic[x] +=1
for v in count_dic.values():
    sum += v*(v-1)//2
for x in A:
    print(sum -(count_dic[x]-1))
### BUGGY CODE ###

h,w = map(int,input().split())
raw = []
for _ in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(2)
  raw.append(add)
nex = [[0,1],[0,-1],[1,0],[-1,0]]
can = []
from copy import deepcopy as dc
for a in range(h):
  for b in range(w):
    if raw[a][b] == 2:
      continue
    now = dc(raw)
    now[a][b] = 1
    ans = 0
    while True:
      last = dc(now)
      ans += 1
      check = 1
      for i in range(h):
        for j in range(w):
          if last[i][j] == 0:
            for x in nex:
              if 0 <= i+x[0] < h and 0 <= j+x[1] < w:
                if last[i+x[0]][j+x[1]] == 1:
                  now[i][j] = 1
                  break
            else:
              check = 0
      if check == 1:
        can.append(ans)
        break
print(max(can))

### FIXED CODE ###

h,w = map(int,input().split())
n = h * w
raw = []
for i in range(h):
  tmp = input()
  add = []
  for j in range(w):
    if tmp[j] == '.':
      add.append(0)
    else:
      add.append(1)
  raw += add
wf = [[1000 for _ in range(n)] for _ in range(n)]
for i in range(n):
  if raw[i] == 0:
    wf[i][i] = 0
    d = []
    if i-w >= 0:
      d.append(i-w)
    if i+w < n:
      d.append(i+w)
    if i%w != 0:
      d.append(i-1)
    if (i+1)%w != 0:
      d.append(i+1)
    for e in d:
      if raw[e] == 0:
        wf[i][e] = 1
#for x in wf:
  #print(x)
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][k] + wf[k][j] < wf[i][j]:
        wf[i][j] = wf[i][k] + wf[k][j]
ans = 0
for i in range(n):
  for j in range(n):
    if ans < wf[i][j] % 1000:
      ans = wf[i][j]
print(ans)
#for x in wf:
  #print(x)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split(' ')))

count = 1
for i in range(1, n):
    if min(P[:i+1]) == P[i]:
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
P = list(map(int, input().split(' ')))

count = 0
minimum = 2 * 10 ** 5 + 1
for p in P:
    if p < minimum:
        count += 1
        minimum = p
print(count)
### BUGGY CODE ###

N = int(input())
List = sorted(list(map(int, input().split())))
for i in range (N):
  for j in range (i+1, N):
    if List[j] == List[i]:
      print("NO")
      break
  else:
    continue
  break
else:
  print("YES")

### FIXED CODE ###

N = int(input())
List = sorted(list(map(int, input().split())))
for i in range(N-1):
  if List[i] == List[i + 1]:
    print("NO")
    break
else:
  print("YES")
### BUGGY CODE ###

z=list(map(int,input().split()))
n=z[0]
y_y=z[1]
y=int(y_y/1000)
for e in range(0,n+1):
    if e*10 <= y:
        x=y-e*10
        for f in range(0,n+1):
            if f*5 <= x:
                z=x-5*f
                for g in range(0,n+1):
                    if g!=z or e+f+g!=n :
                        
                        a,b,c=-1,-1,-1
                    else:
                        
                        a,b,c=e,f,g
                        break
                else:
                    continue
                break
        else:
            continue
        break




print("{0} {1} {2}".format(a,b,c))


### FIXED CODE ###

z=list(map(int,input().split()))
n=z[0]
y_y=z[1]
y=int(y_y/1000)
for e in range(0,n+1):
    if e*10 <= y:
        x=y-e*10
        for f in range(0,n+1):
            if f*5 <= x:
                z=x-5*f
                if z!=n-e-f :
                    a,b,c=-1,-1,-1
                else:
                    a,b,c=e,f,z
                    break
        else:
            continue
        break
      




print("{0} {1} {2}".format(a,b,c))
### BUGGY CODE ###

from heapq import heappush,heappop
from sys import setrecursionlimit
setrecursionlimit(10**6)
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while len(dij)>0:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

### FIXED CODE ###

from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

def check(P):
    for i in range(len(P)-1):
        if P[i] != P[i+1]:
            return i
    return "Non"
P = list(input())
t = check(P)
pop = 0
while t != "Non":
    P.pop(t)
    P.pop(t)
    pop+=1
    t = check(P)
print(pop*2)


### FIXED CODE ###

def check(P):
    for i in range(len(P)-1):
        if P[i] != P[i+1]:
            return i
    return "Non"
def min_2(a,b):
    if a < b:
        return a
    else:
        return b
P = list(input())
c0 = P.count("0")
c1 = P.count("1")
print(min_2(c0,c1)*2)
#t = check(P)
#pop = 0
#while t != "Non":
#    P.pop(t)
#    P.pop(t)
#    pop+=1
#    t = check(P)
#print(pop*2)