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

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
SCORE=[list(map(int,input().split())) for i in range(M)]

SUM=[0]*(N+2)
start=[[] for i in range(N+2)]
end=[[] for i in range(N+2)]

for i in range(M):
    start[SCORE[i][0]].append(i)
    end[SCORE[i][1]+1].append(i)
    SUM[SCORE[i][0]]+=SCORE[i][2]
    SUM[SCORE[i][1]+1]-=SCORE[i][2]

import itertools
SUM=list(itertools.accumulate(SUM))


#遅延Segment tree

for i in range(30):#要素数以上の2のベキを見つける
    if N<1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

SEG=[0 for i in range(2*seg_el-1)]#Segment tree
LAZY=[0 for i in range(2*seg_el-1)]#子ノードへの伝搬用Segment tree

def propagation(k):#一つ下の子へ伝搬
    lazy_item,LAZY[k]=LAZY[k],0
    if 0<=k<seg_el-1:
        LAZY[k*2+1]+=lazy_item
        LAZY[k*2+2]+=lazy_item
        SEG[k*2+1]+=lazy_item
        SEG[k*2+2]+=lazy_item

def update(a,b,x,k,l,r):
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)      
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:
        SEG[k]+=x
        LAZY[k]+=x#そのノードを更新&後でアクセスされたときに子ノードを更新
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)
    SEG[k]=max(SEG[k*2+1],SEG[k*2+2])#そのノードを更新（再帰的に値が求まる）

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,-infを出力
        return -float("inf")
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)
    return max(vl,vr)


for i in range(1,N+2):
    for j in start[i]:
        l,r,s=SCORE[j]
        update(l,r+1,-s,0,0,seg_el)
    for j in end[i]:
        l,r,s=SCORE[j]
        update(l,r+1,s,0,0,seg_el)

    update(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

    #print(SEG)

print(getvalues(0,N+1,0,0,seg_el))
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])
### BUGGY CODE ###

############
#
# N, H
# i : Ai, Bi
#
# currentH <= max(Bi) AND max(Ai, Bi) = Bi then throw i
# currentH <= max(Ai) AND max(Ai, Bi) = Ai then Slash i
# currentH >  max(Bi) AND max(Ai, Bi) = Bi then Slash i
# currentH >  max(Ai) AND max(Ai, Bi) = Ai then Slash i
# 
# 1. select max(Ai, Bi) to Dmg
# 2. currentH = currentH - Dmg
# 2. if Dmg is belong to Bi, then discard Bi
# 3. if currentH > 0, then loop back to 1.

[N, H] = map(int, raw_input().split())

#print N, H

arrayA = []
arrayB = []

for i in range(N):
    [Ai, Bi] = map(int, raw_input().split())
    arrayA.append(Ai)
    arrayB.append(Bi)

arrayA.sort()
arrayB.sort()
arrayA.reverse()
arrayB.reverse()

count = 0

while H > 0:
    maxAi = arrayA[0]
    if len(arrayB) > 0:
        maxBi = arrayB[0]
    else:
        maxBi = 0
    if maxBi > maxAi:
        maxDmg = arrayB.pop(0)
    else:
        maxDmg = maxAi

    H = H -maxDmg
    count = count +1

print count


### FIXED CODE ###

############
#
# N, H
# i : Ai, Bi
#
# currentH <= max(Bi) AND max(Ai, Bi) = Bi then throw i
# currentH <= max(Ai) AND max(Ai, Bi) = Ai then Slash i
# currentH >  max(Bi) AND max(Ai, Bi) = Bi then Slash i
# currentH >  max(Ai) AND max(Ai, Bi) = Ai then Slash i
# 
# 1. select max(Ai, Bi) to Dmg
# 2. currentH = currentH - Dmg
# 2. if Dmg is belong to Bi, then discard Bi
# 3. if currentH > 0, then loop back to 1.

[N, H] = map(int, raw_input().split())

#print N, H

arrayA = []
arrayB = []

for i in range(N):
    [Ai, Bi] = map(int, raw_input().split())
    arrayA.append(Ai)
    arrayB.append(Bi)

arrayA.sort()
arrayB.sort()
arrayA.reverse()
arrayB.reverse()

count = 0

while H > 0:
    maxAi = arrayA[0]
    if len(arrayB) > 0:
        maxBi = arrayB[0]
    else:
        maxBi = 0
        
    if maxBi > maxAi:
        maxDmg = arrayB.pop(0)
        H = H -maxDmg
        count = count +1
    else:
        maxDmg = maxAi
        if maxDmg < H:
            count = count + (H / maxDmg)
            H = H % maxDmg
        else:
            count = count +1
            H = H -maxDmg

#    print H, maxDmg, count

print count
### BUGGY CODE ###

import numpy as np
N, M = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
for b in ab1:
    for a in abN:
        if a == b:
            ok = "POSSIBLE"
print(ok)

### FIXED CODE ###

import numpy as np
N, M = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
if len(set(abN) & set(ab1))>=1:
    ok = "POSSIBLE"
print(ok)
### BUGGY CODE ###

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


### FIXED CODE ###

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

def main():
    from collections import deque
    h,w=map(int,input().split())
    c=eval('list(input()),'*h)
    q=deque()
    for i in range(h):
        for j in range(w):
            if c[i][j]=='#':
                q.append((i,j,0))
    ans=0
    while q:
        y,x,v=q.popleft()
        ans=max(ans,v)
        for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
            if h>i>=0 and w>j>=0 and c[i][j]=='.':
                c[i][j]='#'
                q.append((i,j,v+1))
    print(ans)
if __name__=='__main__':
    main()

### FIXED CODE ###

from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

ok = list()
ans = 0

for i in range(n):
    same = 0
    for j in range(len(ok)):
        if ok[j] == s[i]:
            same = 1
    if same == 1:
        continue
    ok.append(s[i])
    nd = list()
    for j in range(i+1,n):
        same = 0
        for k in range(len(nd)):
            if nd[k] == s[j]:
                same = 1
        if same == 1:
            continue
        nd.append(s[j])
        rd = list()
        for k in range(j+1, n):
            same = 0
            for l in range(len(rd)):
                if rd[l] == s[k]:
                    same = 1
            if same == 1:
                continue
            rd.append(s[k])
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ok = [0,0,0,0,0,0,0,0,0,0]
ans = 0

for i in range(n):
    if sum(ok) == 10:
        break
    if ok[int(s[i])] == 1:
        continue
    ok[int(s[i])] = 1
    nd = [0,0,0,0,0,0,0,0,0,0]
    for j in range(i+1,n):
        if sum(nd) == 10:
            break
        if nd[int(s[j])] == 1:
            continue
        nd[int(s[j])] = 1
        rd = [0,0,0,0,0,0,0,0,0,0]
        for k in range(j+1, n):
            if sum(rd) == 10:
                break
            if rd[int(s[k])] == 1:
                continue
            rd[int(s[k])] = 1
            ans += 1

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

a, b, n = map(int, input().split())
c_0 = 0
m = min(n+1, b)
for x in range(1, m):
  if x % b == 0:
    c = 0
  else:
    c = int(a * x / b)
    if c >= c_0:
      c_0 = c
print(c_0)

### FIXED CODE ###

a, b, n = map(int, input().split())
c_0 = 0
m = min(n, b-1)
x = int(a * m / b)
print(x)
### BUGGY CODE ###

N=int(input())
count=0
A=[]
for K in range(1,N+1):
    for i in range(1,K+1):
        if K%i==0 :
            count+=1
    else:
        x=K*count
        A.append(x)
        count=0
print(sum(A))

### FIXED CODE ###

N=int(input())
A=[]
for i in range(1,N+1):
    x=N//i
    y=i*x*(x+1)/2
    A.append(y)
print(int(sum(A)))
### BUGGY CODE ###

N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input()))

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
#         print(a[i:j])
        if sum(a[i:j]) >= K*(j-i):
            ans += 1
            
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = []
for _ in range(N):
    a.append(int(input())-K)
    
su = 0
v = [(0, 0)]
for i in range(N):
    su += a[i]
    v.append((su, i+1))
v = sorted(v)

data = [0]*(N+5)

def sumation(i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s
    
def add(i, x):
    while i <= N+2:
        data[i] += x
        i += i & -i
ans = 0
for e, i in v:
    ans += sumation(i+1)
    add(i+1, 1)
    
print(ans)
### BUGGY CODE ###

n = int(input())

p = []
for _ in range(n):
    a = input()
    if a in p:
        p.remove(a)
    else:
        p.append(a)
else:
    print(len(p))

### FIXED CODE ###

from collections import Counter as C

n = int(input())
a = C([input() for _ in range(n)])

print(sum([1 for v in a.values() if v % 2]))
### BUGGY CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = '#'
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))


### FIXED CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))
### BUGGY CODE ###

import math
N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
    x[i], y[i] = map(int, input().split())


def mindis(p, q):
    j = 0
    for i in range(N):
        if (x[i]-p)**2+(y[i]-q)**2<(x[j]-p)**2+(y[j]-q)**2:
            j = i
    return j


r = [0 for i in range(N)]
M = 18*10**5
for i in range(M):
    c = math.cos(2*math.pi*i/M)*10**10
    s = math.sin(2*math.pi*i/M)*10**10
    k = mindis(c, s)
    r[k] += 1
S = sum(r)
for i in range(N):
    print(r[i]/S)


### FIXED CODE ###

import math
N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
    x[i], y[i] = map(int, input().split())


def mindis(t):
    j = 0
    for i in range(N):
        if x[i]*math.cos(t)+y[i]*math.sin(t)<x[j]*math.cos(t)+y[j]*math.sin(t):
            j = i
    return j


r = [0 for i in range(N)]
M = 250000
for i in range(M):
    k = mindis(2*math.pi*i/M)
    r[k] += 1
S = sum(r)
for i in range(N):
    print(r[i]/S)
### BUGGY CODE ###

import itertools

n = int(input())
lis = list(input())

ans = list(itertools.combinations(lis, 3))
anss = tuple(set(ans))
print(len(anss))

### FIXED CODE ###

n = int(input())
s = input()

dp1 = [[0 for i in range(10)] for _ in range(n + 1)]
dp2 = [[0 for i in range(100)] for _ in range(n + 1)]
dp3 = [[0 for i in range(1000)] for _ in range(n + 1)]

for i in range(n):
    dp1[i + 1][int(s[i])] = 1
    for j in range(10):
        if dp1[i][j]:
            dp2[i + 1][j * 10 + int(s[i])] = 1
            dp1[i + 1][j] = 1
    for j in range(100):
        if dp2[i][j]:
            dp3[i + 1][j * 10 + int(s[i])] = 1
            dp2[i + 1][j] = 1
    for j in range(1000):
        if dp3[i][j]:
            dp3[i + 1][j] = 1

print(sum(dp3[n]))
### BUGGY CODE ###

#! env python
# -*- coding: utf-8 -*-

import os
import sys


# ac_py.main
# Date: 2020/06/14
# Filename: main 
# Author: acto_mini

def main():
    N = int(input())
    S = input()
    ans = 1000000000
    for i in range(N):
        count = 0
        count += S[0:i].count("W")
        count += S[i+1:N].count("E")
        ans = min(ans, count)

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#! env python
# -*- coding: utf-8 -*-

import os
import sys
from itertools import accumulate


# ac_py.main
# Date: 2020/06/14
# Filename: main 
# Author: acto_mini

def main():
    N = int(input())
    S = input()
    ans = 1000000000

    W = list()
    E = list()
    for i in range(N):
        flag = S[i] == "W"
        W.append(int(flag))
        E.append(int(not flag))

    #
    W_l = accumulate([0] + W[:-1])
    E_r = accumulate([0] + list(reversed(E[1:N])))

    for w, e in zip(W_l, reversed(list(E_r))):
        ans = min(ans, w + e)

    print(ans)
    return


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

def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[0]*2*n 
  for i,c in enumerate(input()[:-1],n):
    data[i]=2**(c-97)
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:
      l,r=int(a)+n-1,int(b)+n
      s=0
      while l<r:
        if l&1:
          s|=data[l]
          l+=1
        if r&1:
          r-=1
          s|=data[r]
        l//=2
        r//=2
      print(bin(s).count('1'))
    else:
      i=int(a)+n-1
      data[i]=2**(b[0]-97)
      i//=2
      while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

from heapq import heappush, heappop


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    h = []
    for a in A:
        heappush(h, [-a, a, 1])
    for i in range(K):
        pri, origlen, cut = heappop(h)
        heappush(h, [-origlen//(cut+1), origlen, cut+1])
    ans = -h[0][0]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def countcut(A, length):
    ret = 0
    for a in A:
        ret += -(-a//length) - 1
    return ret


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    lo = 1
    hi = int(1e9)
    while lo < hi:
        mid = (lo+hi) // 2
        if countcut(A, mid) <= K:
            hi = mid
        else:
            lo = mid + 1
    print(lo)


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

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

if N < M:

    Asym = [0 for i in range(N)]
    sym = 0
    for i, A in enumerate(map(int, input().split())):
        sym = (sym + A) % M
        Asym[i] = sym
    
    ans = Asym.count(0)
    for sym in set(Asym):
        cnt = Asym.count(sym)
        ans +=  int(cnt * (cnt -  1) / 2)
    
    print(ans)

else:

    Acnt = [0 for i in range(M)]
    sym = 0
    for A in map(int, input().split()):
        sym = (sym + A) % M
        Acnt[sym] += 1

    print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))

### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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

g_a = [[] for i in range(n)]
g_b = [[] for i in range(n)]

for i in range(m):
    u,v,a,b = map(int,input().split())
    g_a[u-1].append((a,v-1))
    g_a[v-1].append((a,u-1))
    g_b[u-1].append((b,v-1))
    g_b[v-1].append((b,u-1))

d_a = dijkstra(g_a,n,s-1)
d_b = dijkstra(g_b,n,t-1)

d = []
for i in range(n):
    d.append(d_a[i]+d_b[i])

d.reverse()

for i in range(n):
    print(10**15-min(d))
    d.pop()

### FIXED CODE ###

from heapq import *
from numpy import array,inf


def djikstra(G,s):
    que = []
    d = [inf]*V
    d[s] = 0
    visited = [False] * V
    heappush(que,(0,s))
    while(len(que)!=0):
        p = heappop(que)
        v = p[1]
        if visited[v]:
            continue
        visited[v] = True
        for i in range(len(G[v])):
            e = G[v][i]
            if visited[e[0]]:
                continue
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heappush(que,(d[e[0]],e[0]))
    return d


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

S = djikstra(Ga,s-1)

T = djikstra(Gb,t-1)

M = 10**15-(array(S)+array(T))
ans = [0]*n
ans[n-1] = M[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],M[i])

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

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    t = a[:]
    t.pop(i)
    print(max(t))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a,reverse=True)

for i in range(n):
    if a[i]==b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

H,W,K = map(int,input().split())
S = [input() for i in range(H)]

ans = H+W
for b in range(1<<(H-1)):
    tmp = bin(b).count('1')
    ks = [0]*H
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
    ans = min(ans,tmp)
print(ans)

### FIXED CODE ###

H,W,K = map(int,input().split())
S = [input() for i in range(H)]

ans = H+W
for b in range(1<<(H-1)):
    tmp = bin(b).count('1')
    ks = [0]*H
    valid = True
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
            if any(k > K for k in ks):
                valid = False
                break
    if valid:
        ans = min(ans,tmp)
print(ans)
### BUGGY CODE ###

import collections

mod = 2019

def main():
    S = list(input())
    lenS = len(S)
    Smod2019 = [0] * lenS
    tmp = 0
    for i in range(lenS):
        tmp += (pow(10, i)*int(S[-(i+1)]))
        Smod2019[i] = tmp%mod
    
    cnt = collections.Counter(Smod2019)
    cntitems = cnt.items()
    ans = 0
    #print(cntitems)
    for c in cntitems:
        if c[0] == 0:
            ans += c[1]
        else:
            ans += (c[1] >= 2)*(c[1]-1)
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    S = input()
    N = len(S)
    memo = [0] * 2019
    now = 0
    ten = [0] * 200100
    ten[0] = 1
    for j in range(len(ten)-50):
        ten[j+1] = ten[j]*10%2019

    for i in range(N):
        now += int(S[-(i+1)])*ten[i]
        now %= 2019
        memo[now] += 1
    
    ans = 0
    for k in range(2019):
        ans += (memo[k] * (memo[k]-1)) // 2

    ans += memo[0]
    #m = collections.Counter(memo)
    #print(m)   
    print(ans)


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

def dist(i,j,x,y):
    a = abs(i-j)
    b = abs(x-i) + abs(y-j) + 1
    c = abs(x-j) + abs(y-i) + 1
    return min(a,b,c)

def main():
    N,X,Y = list(map(int,input().split()))

    X -= 1
    Y -= 1
    K = [0 for i in range(N+1)]

    for i in range(N):
        for j in range(N):
            index = dist(i,j,X,Y)
            K[index] += 1

    for i in range(1,N):
        print(int(K[i] / 2))
    

if __name__ == "__main__":
    main()
    


### FIXED CODE ###

def dist(i,j,x,y):
    a = abs(i-j)
    b = abs(x-i) + abs(y-j) + 1
    c = abs(x-j) + abs(y-i) + 1
    return min(a,b,c)

def main():
    N,X,Y = list(map(int,input().split()))

    X -= 1
    Y -= 1
    K = [0 for i in range(N+1)]

    for i in range(N):
        for j in range(N):
            index = dist(i,j,X,Y)
            K[index] += 1

    for i in range(1,N):
        print(int(K[i] / 2))
    

if __name__ == "__main__":
    main()