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

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    k = 1
    while k <= lens:
        ss += (int(s[-k]) * (10 ** (k - 1))) % 2019
        ss = ss % 2019
        d1[ss] += 1
        k += 1
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

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

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

count = 0
i = 0
while i < len(a):
    if a[i] != i + 1:
        a.pop(i)
        count += 1
    else:
        i += 1
if count < N:
    print(count)
else:
    print(-1)

### FIXED CODE ###

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

count = 0
i = 0
d = 0
while i + d < len(a):
    if a[i + d] != i + 1:
        d += 1
        count += 1
    else:
        i += 1
if count < N:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=np.full((h,w),400,np.int64)
ans=0
def bfs(b,i,j,s):
    b[i,j]=0
    seen=np.zeros((h,w),np.int64)
    todo=deque([(i,j)])
    while np.sum(seen)<h*w and len(todo)>0:
        x,y=todo.popleft()
        if seen[x,y]==1:
            continue
        seen[x,y]=1
        if x>0 and seen[x-1,y]==0 and s[x-1][y]=='.':
            b[x-1,y]=b[x,y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1,y]=1
        if x<h-1 and seen[x+1,y]==0 and s[x+1][y]=='.':
            b[x+1,y]=b[x,y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1,y]=1
        if y>0 and seen[x,y-1]==0 and s[x][y-1]=='.':
            b[x,y-1]=b[x,y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x,y-1]=1
        if y<w-1 and seen[x,y+1]==0 and s[x][y+1]=='.':
            b[x,y+1]=b[x,y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x,y+1]=1
    return np.max(b[b<400])

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            b=a
            ans=max(ans,bfs(b,i,j,s))
print(ans)


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[400]*w for _ in range(h)]
ans=0
def bfs(b,i,j):
    b[i][j]=0
    seen=[[0]*w for _ in range(h)]
    todo=deque([(i,j)])
    while len(todo)>0:
        x,y=todo.popleft()
        if seen[x][y]==1:
            continue
        seen[x][y]=1
        if x>0 and seen[x-1][y]==0 and s[x-1][y]=='.':
            b[x-1][y]=b[x][y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1][y]=1
        if x<h-1 and seen[x+1][y]==0 and s[x+1][y]=='.':
            b[x+1][y]=b[x][y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1][y]=1
        if y>0 and seen[x][y-1]==0 and s[x][y-1]=='.':
            b[x][y-1]=b[x][y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x][y-1]=1
        if y<w-1 and seen[x][y+1]==0 and s[x][y+1]=='.':
            b[x][y+1]=b[x][y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x][y+1]=1
    ret=0 
    for bi in b:
        for bij in bi:
            if bij<400:
                ret=max(ret,bij)
    #print(b)
    return ret

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            b=a
            ans=max(ans,bfs(b,i,j))
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
S = list(map(int,input()))
num = 1
T = []
if S[0] == 0:
    T.append(0)
for i in range(1,N):
    if S[i-1] != S[i]:
        T.append(num)
        num = 0
    if i == N-1:
        T.append(num+1)
        continue
    num += 1
if S[N-1] == 0:
    T.append(0)

#index 0,2,4...に1の連続数、1,3,5...に0の連続数
if K >= len(T)//2:
    print(N)
else:
    ans = 0
    for i in range(len(T)//2 -K+1):
        ans = max(ans,sum(T[2*i:2*i+2*K+1]))
    print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
S = list(map(int,input()))
num = 1
T = []
if S[0] == 0:
    T.append(0)
for i in range(1,N):
    if S[i-1] != S[i]:
        T.append(num)
        num = 0
    num += 1
T.append(num)
if S[N-1] == 0:
    T.append(0)
#index 0,2,4...に1の連続数、1,3,5...に0の連続数
if K >= len(T)//2:
    print(N)
else:
    x = sum(T[0:2*K+1])
    ans = x
    for i in range(1,(len(T)//2)-K+1):
        x = x-(T[2*i-2]+T[2*i-1])+(T[2*i+2*K-1]+T[2*i+2*K])
        ans = max(ans,x)
    print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
queue = []
sort_list = [[10**10] for i in range(n)]
for i in range(m):
    a, b = input().split()
    queue.append([int(a), int(b)])
    sort_list[int(a) - 1].append(int(b))

for i in range(n):
    sort_list[i].sort()

for data in queue:
    k, v = map(int, data)   

    num_index = sort_list[k -1].index(v)

    print(str(k).zfill(6) + str(num_index + 1).zfill(6))


### FIXED CODE ###

n, m = map(int, input().split())
queue = []
for i in range(m):
    c, y= map(int, input().split())
    queue.append([c, y, i])

queue = sorted(queue)

index = 0
keep = queue[0][0]
for i in range(m):
    if keep != queue[i][0]:
        index = 0
        keep = queue[i][0]
    index += 1
    queue[i][0] = str(queue[i][0]).zfill(6)
    queue[i][1] = str(index).zfill(6)

queue.sort(key=lambda x: x[2])

for data in queue:
    cn, yn, i = data
    print(cn + yn)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
# print(A)
# print(len(A))

ans = 0
for i in range(len(A)-1):
    tmp = 0
    for j in range(1,len(A)-i):
        # print(A[i],'A[i]',A[i+j],'A[i+j]')
        tmp_ai = A[i] % (10**9 + 7)
        tmp_aij = A[i+j] % (10**9 + 7)
        tmp += (tmp_ai * tmp_aij) % (10**9 + 7)
        # print(tmp,'tmp')
    tmp %= (10**9 + 7)
    ans += tmp

ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

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

sumA = sum(A)
ans = 0
for i in range(len(A)-1):
    sumA -= A[i]
    tmp1 = A[i] % (10**9 + 7)
    tmp2 = sumA % (10**9 + 7)
    ans += tmp1 * tmp2
    ans %= (10**9 + 7)
    
print(ans)
### BUGGY CODE ###

MOD = 1000000007

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

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def xgcd(a, b):
	x0, y0, x1, y1 = 1, 0, 0, 1
	while b != 0:
		q, a, b = a // b, b, a % b
		x0, x1 = x1, x0 - q * x1
		y0, y1 = y1, y0 - q * y1
	return a, x0, y0

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def modinv(a, m):
	g, x, y = xgcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def combination(n, r):
	ans = 1
	for i in range(n - r + 1, n + 1):
		ans *= i
		ans %= MOD
	for i in range(1, r + 1):
		ans *= modinv(i, MOD)
		ans %= MOD
	return ans

ans = 0
ans += 2 ** n - 1
ans += MOD - combination(n, a)
ans += MOD - combination(n, b)
ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 1000000007

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

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def xgcd(a, b):
	x0, y0, x1, y1 = 1, 0, 0, 1
	while b != 0:
		q, a, b = a // b, b, a % b
		x0, x1 = x1, x0 - q * x1
		y0, y1 = y1, y0 - q * y1
	return a, x0, y0

# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def modinv(a, m):
	g, x, y = xgcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def combination(n, r):
	ans = 1
	for i in range(n - r + 1, n + 1):
		ans *= i
		ans %= MOD
	for i in range(1, r + 1):
		ans *= modinv(i, MOD)
		ans %= MOD
	return ans

ans = 0
ans += pow(2, n, MOD) - 1
ans += MOD - combination(n, a)
ans += MOD - combination(n, b)
ans %= MOD

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

S=input()
x=0
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[1][0]=1
for i in range(len(S)):
  dp[0]=[0]*13
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[1]):
        dp[0][(j+s)%M]+=d
        dp[0][(j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[1]):
      dp[0][(j+s)%M]=d
  for j,d in enumerate(dp[0]):
    dp[1][(10*j)%M]=d
print(dp[0][5]%MOD)



### FIXED CODE ###

S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = []
C = []
for i in range(0,M):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)

A.sort()

for i in range(0,M):
    for j in range(0,B[i]):
        if C[i] > A[j]:
            A[j] = C[i]
        else:
            break
    A.sort()

result = 0
for num in A:
    result += num
print(result)


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
cards = []
for i in range(0,N):
    cards.append((A[i],1))

for i in range(0,M):
    b,c = map(int,input().split())
    cards.append((c,b))

cards.sort()
cards.reverse()

result = 0
total = N
for num, cnt in cards:
    total -= cnt
    result += num*cnt
    if total < 0:
        result += num * total
        break
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,k,X):
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        return max(X[1][1]*i + X[0][1]*((N-i*X[1][0])//X[0][0]) + (N-i*X[1][0])%X[0][0] for i in range(N//X[1][0]+1))
    if k == 3:
        dp = np.zeros((3, N+1), dtype=int)
        M = np.arange(N+1)
        dp[0] = X[0][1]*(M//X[0][0]) + M%X[0][0]
        d = X[1][1]*(M//X[1][0]) + M%X[1][0]
        for w in range(1, N+1):
            dp[1,w] = np.max(dp[0,w::-1] + d[:w+1])
        return np.max(dp[1,::-1] + X[2][1]*(M//X[2][0]) + M%X[2][0])

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, len(X), X)
    res = N

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

import bisect
N = int(input())
Ln = list(map(int,input().split(' ')))

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    Ln.sort(reverse=True)
    count = 0
    for a in range(N):
        a_l = Ln[a]
        current_min = N-1
        b = a +1
        while b <= current_min:
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                b += 1
                continue
            current_min -= 1
    print(count)

def main3():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            c_list = Ln[0:b_idx+1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

main3()

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

import numpy as np


def main():
    N, W = map(int, input().split())

    w = []
    v = []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    dp = np.zeros((N, W + 1), dtype='int')
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    print(dp[-1][-1])
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# メイン関数
def main():
    # 入力データ
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        wi, vi = map(int, input().split())
        w.append(wi)
        v.append(vi)

    # dpテーブルの作成
    dp = [[0] * (W+1) for i in range(N)]
    for i in range(N):
        for j in range(W + 1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    # 解答の出力
    print(dp[-1][-1])
    return

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

#create date: 2020-04-26 21:06

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    s = ni()
    n = len(str(s))
    now = 0
    m = [0] * 2019
    for i in range(n):
        now = (s % 10**(i+1)) % 2019
        #print(now)
        m[now] += 1
    ans = m[0]
    for mi in m[1:]:
        ans += (mi-1) * mi //2
    print(ans)

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-04-26 21:06

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    s = ns()
    n = len(s)
    now = 0
    m = [0] * 2019
    for i in range(n):
        now = (now + int(s[n-i-1]) * pow(10, i, 2019)) % 2019
        #print(now)
        m[now] += 1
    m[0] += 1
    ans = 0
    for mi in m:
        ans += (mi-1) * mi //2
    print(ans)

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

N = int(input())
A = [int(i) for i in input().split()]
A1 = 1
for j in range(N):
    A1 *= A[j]
if A1>10**18:
    print(-1)
else:
    print(A1)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
A1 = 1
if 0 in A:
    print(0)
else:    
    for j in range(N):
        A1 *= A[j]
        if A1>10**18:
            print(-1)
            break
    else:
        print(A1)
### BUGGY CODE ###

import numpy as np

def main():

    S = np.array(list(input()))

    r = False
    for i in range(int(input())):
        Query = input().split()
        if Query[0] == "1":
            r = not r
        else:
            if (r==False and Query[1] == "1") or (r==True and Query[1] == "2"):
                S = np.append(Query[2],S)
            else:
                S = np.append(S,Query[2])

    if r == True:
        S = np.flipud(S)

    S = "".join(S)

    print(S)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():

    S = deque(list(input()))

    r = False
    for i in range(int(input())):
        Query = input().split()
        if Query[0] == "1":
            r = not r
        else:
            if (r==False and Query[1] == "1") or (r==True and Query[1] == "2"):
                S.appendleft(Query[2])
            else:
                S.append(Query[2])

    if r == True:
        S.reverse()

    print("".join(list(S)))


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

import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = []
for i in range(1, n + 1):
    cost.append([yen[i] + snu[i],i])

cost.sort(key = lambda x: x[0])

for i in range(1, n + 1):
    for j in cost:
        if j[1] >= i:
            print(1000000000000000 - j[0])
            break

### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

from math import ceil
from bisect import bisect_right
n, d, a = map(int, input().split())
l = []
l2 = []
l3 = []
ans = 0
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])
  l2.append(x + 2 * d)
  l3.append(x)
l.sort(key=lambda x: x[0])
l2.sort()
l3.sort()
for i in range(n):
  if l[i][1] == 0:
    continue
  else:  
    cnt = ceil(l[i][1] / a)
    ans += cnt
    ind = bisect_right(l3, l2[i])
    for j in range(i, ind):
      l[j][1] = max(0, l[j][1] - a * cnt)
print(ans)

### FIXED CODE ###

from math import ceil
from bisect import bisect_right

n, d, a = map(int, input().split())
l = []
l2 = []
l3 = []
l4 = [0 for i in range(n+1)]
l5 = [0 for i in range(n+1)]
ans = 0
for i in range(n):
  x, h = map(int, input().split())
  l.append([x, h])
  l2.append(x + 2 * d)
  l3.append(x)
l.sort(key=lambda x: x[0])
l2.sort()
l3.sort()
for i in range(n):
  cnt = ceil((l[i][1] - l4[i] * a) / a)
  if cnt > 0:
    ans += cnt
    ind = bisect_right(l3, l2[i])
    l5[ind] += cnt
    l4[i] += cnt
  l4[i+1] = l4[i] - l5[i+1]
    
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import math

n = int(input())

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

A.sort()
B.sort()
C.sort()

Bc, Cc = [0]*n, [0]*n

for i in range(n):
    for j in range(n):
        if A[i] < B[j]:
            Bc[i] = n - j
            break
    for j in range(n):
        if B[i] < C[j]:
            Cc[i] = n - j
            break

count = 0
for bc in Bc:
    count += sum(Cc[n-bc:])

print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import bisect
 
n = int(input())
 
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
 
Ac, Cc = [0]*n, [0]*n
# Ap, Cp = 0, 0
 
for i in range(n):
    Ac[i] = bisect.bisect_left(A, B[i])#[Ap:], B[i])
    # Ac[i], Ap = index + Ap, index + Ap
    Cc[i] = n - bisect.bisect_right(C, B[i])#[Cp:], B[i])
    # Cc[i], Cp = n - index - Cp, index + Cp
 
 
count = 0
for i in range(n):
    count += Ac[i]*Cc[i]
 
print(count)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = X.copy()
Y.sort()

for i in X:
    if Y.index(i) >= N//2:
        print(Y[N//2-1])
    if Y.index(i) <= N//2 - 1:
        print(Y[N//2])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = X.copy()
Y.sort()

l = Y[N//2-1]
r= Y[N//2]

for i in X:
    if i <= l:
        print(r)
    else:
        print(l)