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

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()


def binary_search(k, x):
    index = bisect.bisect_right(k, x)
    if index == len(k):
        return False
    else:
        # index + 1個している
        return index + 1


ans = 0
for up in a:
    indexed_b = binary_search(b, up)
    b_cnt = n - (indexed_b - 1)
    if b_cnt > len(b):
        break
    for middle in b[indexed_b-1:]:
        indexed_c = binary_search(c, middle)
        c_cnt = n - (indexed_c - 1)
        ans += c_cnt

print(ans)


### FIXED CODE ###

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()


def binary_upper(k, x):
    return len(k) - bisect.bisect_right(k, x)


def binary_lower(k, x):
    return bisect.bisect_left(k, x)


ans = 0

for middle in b:
    cnt_a = binary_lower(a, middle)
    cnt_c = binary_upper(c, middle)
    ans += cnt_a * cnt_c

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

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

dp = [""] * (n+1)
dp[0] = "0"
ma = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(n):
    if dp[i] == "":
        continue
    elif dp[i] == "0":
        for j in a:
            k = i + ma[j]
            if k <= n:
                if dp[k] == "":
                    dp[k] = "0"
                dp[k] = max(dp[k], str(j), key=int)
    else:
        for j in a:
            k = i + ma[j]
            if k <= n:
                if dp[k] == "":
                    dp[k] = "0"
                dp[k] = max(dp[k], dp[i] + str(j), key=int)
                dp[k] = max(dp[k], str(j)+dp[i], key=int)

print(dp[-1])


### FIXED CODE ###

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

dp = [(0, 0)] * (n+1)
ma = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(n):
    if i!=0 and dp[i] == (0, 0):
        continue
    for j in a:
        t = dp[i]
        k = i + ma[j]
        if k <= n:
            dp[k] = max(dp[k], (t[0] + j * 10 ** t[1], t[1] + 1))
            dp[k] = max(dp[k], (t[0]*10 + j, t[1] + 1))

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

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

cont = 0
for x in range(k+1):
    for y in range(k+1):
        if x + y <= s:
            for z in range(k+1):
                if s == (x + y + z):
                    cont += 1
print(cont)

### FIXED CODE ###

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

cont = 0
for x in range(k+1):
    for y in range(k+1):
        if x + y <= s:
            if s - (x+y) <= k:
                cont += 1
print(cont)
### BUGGY CODE ###

a = int(input())
b = input().split()
c = 1
for i in range(a):
    c = c*int(b[i])

if c > 1000000000000000000:
    print(-1)
else:
    print(c)    

### FIXED CODE ###

a = int(input())
b = input().split()
c = 1
for i in range(a):
    if int(b[i]) == 0:
        c = 0

if c == 1:
    for i in range(a):
        c = c*int(b[i])
        if c > 1000000000000000000:
            break

if c > 1000000000000000000:
    print(-1)
else:
    print(c)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

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

pref = [[] for _ in range(N)]

res = []

for i in range(M):
    p, y = map(int, input().split())
    pref[p-1].append(y)
    res.append((p-1, y))

for ar in pref:
    ar.sort()

for pre, year in res:
    p = str(pre + 1)
    p_zero = p.zfill(6)
    y = str(pref[pre].index(year) + 1)
    y_zero = y.zfill(6)
    print(p_zero + y_zero)

### FIXED CODE ###

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

L = [[] for i in range(N)]
D = []

for i in range(M):
    p, y= map(int, input().split())
    L[p-1].append(y)
    D.append([p,y])

for i in range(N):
    L[i].sort()

for i in range(M):
    ans = str(D[i][0]).zfill(6)+ str(bisect.bisect_left(L[D[i][0]-1], D[i][1])+1).zfill(6)
    print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,x = LI()
    a = sorted(LI(), reverse=True)
    d = collections.defaultdict(int)
    d[(x,0)] = 1

    fm = {}
    def f(i):
        if i < 2:
            return 1
        if i in fm:
            return fm[i]
        r = i * f(i-1) % mod
        fm[i] = r
        return r

    for ai in range(n):
        c = a[ai]
        e = collections.defaultdict(int)
        for kk,v in d.items():
            k,i = kk
            if ai < n-1:
                e[(k,i+1)] += v
                e[(k,i+1)] %= mod
            kc = k % c
            e[(kc,i)] += v
            e[(kc,i)] %= mod
            for j in range(i-1,-1,-1):
                e[(kc,j)] += v * f(i) // f(j)
                e[(kc,j)] %= mod
        d = e

    r = 0
    for kk,v in d.items():
        k,i = kk
        if i > 0:
            continue
        r += k * v
        r %= mod

    return r


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,x = LI()
    a = sorted(LI(),reverse=True)
    d = collections.defaultdict(int)
    d[x] = 1
    for i in range(n):
        c = a[i]
        e = collections.defaultdict(int)
        for k,v in d.items():
            e[k] += v * (n-i-1)
            e[k] %= mod
            e[k%c] += v
            e[k%c] %= mod

        d = e

    r = 0
    for k,v in d.items():
        r += k * v
        r %= mod

    return r


print(main())
### BUGGY CODE ###

import itertools
L,R=map(int,input().split())

A=[]
D=[]

for i in range(R-L+1):
    A.append((i+L)%2019)

if A.count(1)>=2:
    B=set(A)
    B.add(1)
else:
    B=set(A)

C=list(itertools.combinations(B,2))
for j in range(len(C)):
    D.append(C[j][0]*C[j][1]%2019)
E=sorted(D)
print(E[0])


### FIXED CODE ###

import itertools
L,R=map(int,input().split())

A=[]
D=[]

if R-L+1<2019:
    for i in range(R-L+1):
        A.append((i+L)%2019)

    if A.count(1)>=2:
        B=set(A)
        B.add(1)
    else:
        B=set(A)

    C=list(itertools.combinations(B,2))
    for j in range(len(C)):
        D.append(C[j][0]*C[j][1]%2019)
    E=sorted(D)
    print(E[0])
else:
    print(0)
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


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

n = int(input())
a = sorted(list(map(int, input().split())))
q = int(input())
l1 = [0]*(10**5+10)
l2 = [0]*(10**5+10)
index = 0
l1[0] = a[0]
l2[0] = 1
for i in a[1:]:
    if i == l1[index]:
        l2[index] += 1
    else:
        index += 1
        l1[index] = i
        l2[index] = 1
s = sum(a)
for _ in range(q):
    b, c = map(int, input().split())

    i = 0
    while i < index + 2:
        if (b == l1[i]):
            break
        i += 1
    if i > index:
        print(s)
        continue

    j = 0
    while j < index + 2:
        if(c == l1[j]):
            break
        j += 1
    if j > index:
        index = j
        l1[index] = c
    s += (c - b) * l2[i]
    l2[j] += l2[i]
    l2[i] = 0
    print(s)


### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
q = int(input())
l = [0]*(10**5+10)
for i in a:
    l[i] += 1
s = sum(a)
for _ in range(q):
    b, c = map(int, input().split())
    s += (c - b) * l[b]
    l[c] += l[b]
    l[b] = 0
    print(s)
### BUGGY CODE ###

H, W, M = map(int, input().split())
hn = {}
wn = {}
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  if (h,w) not in flag: 
    if h in hn:
      hn[h] += 1
    else:
      hn[h] = 1
    if w in wn:
      wn[w] += 1
    else:
      wn[w] = 1
  flag.add((h,w))
  
hrank = sorted(hn.items(), key=lambda t:-t[1])
wrank = sorted(wn.items(), key=lambda t:-t[1])

hmax = hrank[0][1]
wmax = wrank[0][1]

hmaxlist =[]
for k,v in hrank:
  if v == hmax:
    hmaxlist.append(k)
  else:
    break

wmaxlist =[]
for k,v in wrank:
  if v == wmax:
    wmaxlist.append(k)
  else:
    break

flag2 = set()
for i in hmaxlist:
  for j in wmaxlist:
    flag2.add((i,j))

if len(flag2 - flag) == 0:
  print(hmax+wmax -1)
else:
  print(hmax+wmax)

### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
hn = [0]*H
wn = [0]*W
flag = set()
for i in range(M):
  h, w = map(int, input().split())
  hn[h-1] += 1
  wn[w-1] += 1
  flag.add((h,w))
  
#hrank = sorted(hn, key=lambda t:-t[1])
#wrank = sorted(wn, key=lambda t:-t[1])

hmax = max(hn)
wmax = max(wn)

hmaxlist = {i+1 for i,h in enumerate(hn) if h == hmax}
#for h in hn:
#  if h == hmax:
#    hmaxlist.append(h)
  
wmaxlist = {i+1 for i,w in enumerate(wn) if w == wmax}
#for w in wn:
#  if w == wmax:
#    wmaxlist.append(w)
  

for i in hmaxlist:
  for j in wmaxlist:
    if (i,j) not in flag:
      print(hmax+wmax)
      sys.exit()
print(hmax+wmax-1)
### BUGGY CODE ###

import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) #tdは同値類がキーで中の元が値
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] #da,dbはa,bの含まれる同値流のラベル
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        else:
            td[da].extend(td[db])
            for x in td[db]:
                d[x]=da

    return list(d.values())

def main(n,k,l,e1,e2):
    d1=conn(n,k,e1)
    d2=conn(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    # print(d1,d2,d,p)
    d[(k,l)]=1
    print(' '.join([str(d[x]) for x in p]))

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)


### FIXED CODE ###

import sys
from collections import deque
from collections import defaultdict
from collections import Counter

def conn(n,m,e):
    d=dict(zip(range(1,n+1),range(-1,(-1)*n-1,-1)))
    td=defaultdict(lambda:deque([])) #tdは同値類がキーで中の元が値
    c=1
    for edge in e:
        a=edge[0]
        b=edge[1]
        da=d[a] #da,dbはa,bの含まれる同値流のラベル
        db=d[b]
        if da<0 and db<0:
            d[a]=c
            d[b]=c
            td[c].append(a)
            td[c].append(b)
            c+=1
        elif da>0 and db<0:
            d[b]=da
            td[d[a]].append(b)
        elif da<0 and db>0:
            d[a]=db
            td[d[b]].append(a)
        elif da>0 and db>0 and da!=db:
            for x in td[db]:
                d[x]=da
                td[da].append(x)

    return list(d.values())

def main(n,k,l,e1,e2):
    d1=conn(n,k,e1)
    d2=conn(n,l,e2)
    p=tuple(zip(iter(d1),iter(d2)))
    d=Counter(p)
    # print(d1,d2,d,p)
    d[(k,l)]=1
    print(' '.join([str(d[x]) for x in p]))

if __name__=='__main__':
    ssr=sys.stdin.readline
    n,k,l=map(int,ssr().strip().split())
    e1=[]
    e2=[]
    for _ in range(k):
        e1.append(tuple(map(int,ssr().strip().split())))
    for _ in range(l):
        e2.append(tuple(map(int,ssr().strip().split())))
    main(n,k,l,e1,e2)
### BUGGY CODE ###

N,M = map(int, input().split())
L = []
R = []
for idx in range(M):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)

lst = []
result = 0
for idx in range(M):
    lst.append(range(L[idx],R[idx]+1))
for id in range(1,N+1):
    flag = True
    for i in range(M):
        if (id in lst[i]) == False:
            flag = False
            break
    if flag == True:
        result += 1
print(result)

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
l,r = [], []
for i in range(m):
    a,b = MAP()
    l.append(a)
    r.append(b)

max_l = max(l)
min_r = min(r)
if min_r<max_l:
    print(0)
    exit()
print(min_r-max_l+1)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
digits = [0] * 60
ans = 0
for ai in a:
    temp = ai
    num = len(bin(temp)) - 2
    for i in range(num):
        if (temp >> i) & 1:
            digits[i] += 1
    ans += (n - 1) * temp
    ans = ans % mod

for i in range(60):
    digit = digits[i]
    temp = digit * (digit - 1) * pow(2, i, mod)
    ans -= temp % mod
print(ans % mod)
#print(digits)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=tuple(map(int,input().split()))
mod=10**9+7
cnt=[0]*60

for temp in a:
    if temp==0:continue
    digit=len(bin(temp))-2
    for j in range(digit):
        if (temp>>j)&1:
            cnt[j]=cnt[j]+1

#print(cnt)
ans=0
for i in range(60):
    if cnt[i]==0:continue
    ans=(ans+pow(2,i)*cnt[i]*(n-cnt[i]))%mod
print(ans%mod)
### BUGGY CODE ###

# import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))
for i in range(len(P)):
	P[i] = (P[i] + 1) * 0.5
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print(maxv)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = tempsum = sum(P[:k])
for i in range(1, n-k+1):
	tempsum = tempsum - P[i-1] + P[i+k-1]
	maxv = max(maxv, tempsum)
print((maxv + k) * 0.5)
### BUGGY CODE ###

import collections
n = int(input())
ls = [input() for i in range(n)]    
c = collections.Counter(ls)
count = c.most_common()[0][1]
ans = []
if c.most_common()[0][1] == 1:
    ls.sort()
    for i in ls:
        print(i)
elif c.most_common()[-1][1] == 2 and c.most_common()[0][1] == 2:
    ls.sort()
    for i in ls:
        print(i)
elif c.most_common()[-1][1] == 3 and c.most_common()[0][1] == 3:
    ls.sort()
    for i in ls:
        print(i)
else:
    for i in range(len(c)):
        p = c.most_common()
        if p[i][1] == count:
            ans.append(p[i][0])
        else:
            break   
    ans.sort()
    for i in ans:
      print(i)

### FIXED CODE ###

import collections
from collections import Counter

n = int(input())
ls = [input() for i in range(n)]    
c = Counter(ls).most_common()

count = c[0][1]
ans = []

for i in range(len(c)):
    if c[i][1] == count:
        ans.append(c[i][0])
    else:
        break   
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

N, K = [int(item) for item in input().split()]
h =np.array([int(item) for item in input().split()])

dp = np.full(N+1, 10**10+1, dtype='int64')
dp[0] = 0

for i in range(1, N):
    start = max(0, i-K)
    cost = abs(h[start:i] - h[i])
    dp[i] = min(dp[start:i] + cost)

    # print(dp)
print(dp[N-1])

### FIXED CODE ###

import numpy as np

N, K = [int(item) for item in input().split()]
h =np.array([int(item) for item in input().split()])
# print(h.shape)
dp = np.full(N+K, 10**10+1, dtype='int64')
dp[0] = 0

for i in range(1, N):
    max1 = min(N, i+K)
    cost = abs(h[i:max1] - h[i-1])
    # print(cost.shape, dp[i:max1].shape)
    dp[i:max1] = np.minimum(dp[i:max1], dp[i-1] + cost)

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


s=list(input())
l=len(s)
mod=10**9+7
dp=[0]*13
dp[0] = 1
mul=1
for i in s[::-1]:
    nextDp=[0]*13
    if i=="?":
        for k in range(10):
            for j in range(13):
                nextDp[(k*mul+j)%13] += dp[j]
                nextDp[(k*mul+j)%13]%=mod
    else:
        for j in range(13):
            nextDp[(int(i)*mul+j)%13] += dp[j]
            nextDp[(int(i)*mul+j)%13]%=mod
    mul *= 10
    dp = nextDp

print(dp[5])

### FIXED CODE ###

MOD = 10**9 + 7
S = input()
 
cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13
 
    r = (10 * r) % 13
 
print(cur[(5-base) % 13])
### BUGGY CODE ###

from itertools import permutations
import sys
INF = float('inf')
n, m, R = map(int, sys.stdin.readline().split())
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a][b] = c
    dist[b][a] = c
    
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dist[i][j] > dist[i][k]+dist[k][j]:
                dist[i][j] = dist[i][k]+dist[k][j]
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))
### BUGGY CODE ###

import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    prevs = [-1 for _ in range(n+1)]
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            alt = costs[u] + c
            if alt < costs[v]:
                prevs[v] = u
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [y+s for y, s in zip(cost_y, cost_s)]
result = [float('inf') for _ in range(n+1)]
min_cost = result[-1]
for i in range(n, 0, -1):
    if min_cost > cost_ys[i]:
        min_cost = cost_ys[i]
    result[i] = min_cost
yen = 10**15
for i in range(1, n+1):
    print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

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

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
### BUGGY CODE ###

N = int(input())

flag = 0
res = 0
while N > 0:
	n = N % 10
	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n
		
	N = N // 10

if flag == 1:
	print(res + 1)
else:
	print(res)

### FIXED CODE ###

N = input()

nagasa = len(N)
flag = 0
res = 0
for i in range(nagasa):
	s = nagasa - i - 1
	n = int(N[s])

	if flag == 2:
		if n <= 4:
			flag = 0
			res += n
		elif n == 5:
			flag = 1
			res += 4
		elif n >= 6:
			flag = 1
			res += 9 - n
	else:
		if flag == 1:
			n += 1
		if n == 5:
			flag = 2
			res += 5
		elif n > 5:
			flag = 1
			res += 10 - n
		else:
			flag = 0
			res += n

if flag == 1:
	print(res + 1)
else:
	print(res)
### BUGGY CODE ###

N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

c = 0

if A == B:
    print(c)
    exit()

# A[i] < B[i]のところはA[i] == 0になるまで追いつけない
for i in range(N):
    if A[i] < B[i]:
        c += A[i]
        B[i] -= A[i]
        A[i] = 0

while A != B:
    x = 0
    for i in range(N):
        if A[i] == 0:
            continue
        x = i
        if A[i] < B[i]:
            break
    A[x] -= 1
    y = 0
    for i in range(N):
        if A[i] == B[i]:
            continue
        y = i
        if A[i] < B[i]:
            break
    B[y] -= 1
    c += 1

print(c)


### FIXED CODE ###

N = int(input())

same = True
sum_a = 0
min_b = None

for _ in range(N):
    a, b = map(int, input().split())
    # Aの総和を求める
    sum_a += a
    # AとBが等しいどうかを調べる
    if a != b:
        same = False
    # Ai > Biの中で最小のbを求める
    if a > b and (min_b is None or b < min_b):
        min_b = b

# 初めから同じなら手数なし
if same:
    print(0)
    exit()

# Ai > Biの中で最小のbを求める
if min_b is None:
    min_b = 0

print(sum_a - min_b)
### BUGGY CODE ###

a, b, c, k = input().split()
a, b, c, k = int(a), int(b), int(c), int(k)
result = 0

for i in range(k):
    if a != 0:
        result = result + 1
        a = a - 1
    elif a == 0 and b != 0:
        #result変わらず
        b = b - 1
    elif a == 0 and b == 0 and c != 0:
        result = result - 1
        c = c - 1
    else:
        break

print(result)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

if a >= k:
    print(k)
    exit()

if k-a-b <= 0:
    print(a)
    exit()

print(a-(k-a-b))