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

import sys
sys.setrecursionlimit(3001)

N = int(input())
p_f = [0]
p_b = [0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

p_majority = 0.0
n_majority = N // 2 + 1

def cointoss(n_toss,n_front,n_back,p):
    global p_majority
    n_toss += 1
    #print(n_toss,n_front,n_back,p,p_majority,n_majority)
    if n_front+1 == n_majority:
        p_majority = p_majority + p * p_f[n_toss]
    else:
        cointoss(n_toss, n_front+1, n_back, p*p_f[n_toss])
    if n_back+1 == n_majority:
        return
    cointoss(n_toss, n_front, n_back+1, p*p_b[n_toss])

cointoss(0,0,0,1.0)
print(p_majority)


### FIXED CODE ###

N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

#一次軸：コイントスの回数、二次軸：勝ち数、値：発生確率
dp = [[0.0] * (N+1) for i in range(N+1)]
dp[0][0] = 1.0

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)
### BUGGY CODE ###

#!/usr/bin/env python3
#SoundHound D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,s,t = LI()
graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = LI()
    graph1[u-1].append((v-1,a))
    graph1[v-1].append((u-1,a))
    graph2[u-1].append((v-1,b))
    graph2[v-1].append((u-1,b))

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

c1 = dijkstra(s-1,graph1)
c2 = dijkstra(t-1,graph2)
c = [c1[i] + c2[i] for i in range(n)]
money = 10**15
for i in range(n):
    ans = money - min(c[i:])
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#SoundHound D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,s,t = LI()
graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
for _ in range(m):
    u,v,a,b = LI()
    graph1[u-1].append((v-1,a))
    graph1[v-1].append((u-1,a))
    graph2[u-1].append((v-1,b))
    graph2[v-1].append((u-1,b))

def dijkstra(s,graph):
    d = [inf]*n
    d[s] = 0
    h = [(0,s)]
    while h:
        c,v = heappop(h)
        if d[v] < c:
            continue
        for t,cost in graph[v]:
            if d[v] + cost < d[t]:
                d[t] = d[v] + cost
                heappush(h,(d[t],t))
    return d

c1 = dijkstra(s-1,graph1)
c2 = dijkstra(t-1,graph2)
c = [c1[i] + c2[i] for i in range(n)]
money = 10**15
mi = c[-1]
for i in range(n-1)[::-1]:
    mi = min(mi,c[i])
    c[i] = mi
for i in range(n):
    print(money - c[i])
### BUGGY CODE ###

MOD = 10**6+3
n = MOD + 10
fac = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD

q = int(input())

def f(x, d, n):
    if d == 0:
        return pow(x, n, MOD)
    p = (x * pow(d, MOD-2, MOD)) % MOD
    if p + n - 1 >= MOD:
        return 0
    q = fac[(p + n - 1) % MOD]
    r = fac[p - 1]
    s = pow(d, n, MOD)
    return (q*pow(r, MOD-2, MOD)*s) % MOD

for i in range(q):
    x, d, n = [int(item) for item in input().split()]
    print(f(x, d, n))

### FIXED CODE ###

MOD = 10**6+3
n = MOD + 10

fac = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * i % MOD

q = int(input())

def f(x, d, n):
    if d == 0:
        return pow(x, n, MOD)
    p = (x * pow(d, MOD-2, MOD)) % MOD
    if p + n - 1 >= MOD:
        return 0
    q = fac[(p + n - 1) % MOD]
    r = fac[p - 1]
    s = pow(d, n, MOD)
    return (q*pow(r, MOD-2, MOD)*s) % MOD

for i in range(q):
    x, d, n = [int(item) for item in input().split()]
    print(f(x, d, n))
### BUGGY CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] = (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = 0 #even
  return sn

base = create_list()
#print(base)
for i in range(Q):
  if(l[i]==r[i]):
    print(base[l[i]])
  else:
    lnum = base[0:l[i]]
    rnum = base[0:r[i]]
    print( sum(rnum)-sum(lnum) )

### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)

Q = int(input())

l = [0 for _ in range(Q)]
r = [0 for _ in range(Q)]
i = 0
while True:
  try:
    lr=list(map(int,input().split()))
    l[i] = lr[0]
    r[i] = lr[1]
    i+=1
  except:
    break

def is_prime(num):
  #if(type(num) != type(0)):
  #  print('error at '+str(num)+' type = '+str(type(num)))
  #  print(type(int))
  #  return 0
  #if(num<2):
  #  return 0
  if(num == 2):
    return 1
  n = math.ceil(math.sqrt(num))
  for i in range(2,n+1):
    if((num%i) == 0):
      return 0
  return 1

def create_list():
  MAXI = max(r)+1
  
  prime = [1 for _ in range(MAXI+1)]
  prime[0] = 0
  prime[1] = 0
  for i in range(2,MAXI):
    if(prime[i] == 0):
      continue
    else:
      prime[i] = is_prime(i)
      for j in range(i*2,MAXI,i*2):
        prime[j] = 0
      for j in range(i*5,MAXI,i*3):
        prime[j] = 0
      for j in range(i*5,MAXI,i*5):
        prime[j] = 0
  #print(prime)
  sn = [0 for _ in range(MAXI+2)]
  for i in range(1,MAXI+1,2):
    #print('int(('+str(i+1)+')/2) = '+str(int((i+1)/2))+' when '+str(prime[int((i+1)/2)]))
    sn[i] += sn[i-1] + (prime[i] * prime[int((i+1)/2)]) #odd
    sn[i+1] = sn[i]
  return sn

base = create_list()
#print(base)
for i in range(Q):
  print( base[r[i]] - base[l[i]-1] )#sum(rnum)-sum(lnum) )
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
x = []
for i in range(m):
    b, c = map(int, input().split())
    x += [c]*b
x.sort(reverse=True)

ans = 0
for i in range(n):
    if i >= len(x):
        ans += a[i]
    else:
        ans += max(a[i], x[i])

print(ans)


### FIXED CODE ###

from collections import Counter


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

for i in range(m):
    b, c = map(int, input().split())
    x[c] += b

y = list(zip(x.keys(), x.values()))
y.sort(reverse=True)

ans = 0
k = 0
for z in y:
    if k + z[1] <= n:
        ans += z[0] * z[1]
        k += z[1]
    else:
        ans += z[0] * (n - k)
        k = n
        break
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
max=0
t=list(input().split())
s=[int(n) for n in t]
for i in range(N-K+1):
    x=0
    for j in range(K):
        x+=s[i+j]
    if max<x :
        max=x
print((max+K)/2)

### FIXED CODE ###

N, K = map(int,input().split())
t=list(input().split())
s=[int(n) for n in t]
max=x=sum(s[:K])
for i in range(N-K):
    x+=(s[K+i]-s[i])
    if max<x :
        max=x
print((max+K)/2)
### BUGGY CODE ###

import sys

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = IL()
	h_i = IL()
	dp = [0] * N
	for i in range(1, N):
		dp[i] = min([abs(h_i[i] - h_i[i-j]) + dp[i-j] for j in range(1, min(i, K)+1)])
		
	return dp[-1]


if __name__ == "__main__":
	print(main())

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[0 for i in range(N)] for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	
	A[u].append(v)
	A[v].append(u)
	W[u][v] = w
	W[v][u] = w

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][j]

for i in l:
	print('{}'.format(i%2))

### FIXED CODE ###

N = int(input())
q = []
c = [0 for i in range(N)]
l = [0 for i in range(N)]
A = [[] for i in range(N)]
W = [[] for i in range(N)]

for i in range(N-1):
	u, v, w = map(int,input().split())
	u = u - 1
	v = v - 1
	
	A[u].append(v)
	A[v].append(u)
	W[u].append(w)
	W[v].append(w)

q.append(0)
while len(q):
	i = q.pop(0)
	c[i] = 1
	k = 0
	for j in A[i]:
		if c[j] == 0:
			q.append(j)
			l[j] = l[i] + W[i][k]
		k = k + 1

for i in l:
	print('{}'.format(i%2))
### BUGGY CODE ###

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

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort(reverse=True)
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
    print(cnt)

if (__name__ == "__main__"):
    main()

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))

def meguru_nibutan(ar,m,key):
    a = m
    b = len(ar)
    while(abs(a-b) > 1):
        c = (a+b)//2
        if (ar[c] > key):
            a = c
        else:
            b = c
    return a

def main():
    cnt = 0
    l.sort()
    for a in range(0,n-2):
        for b in range(a+1,n-1):
            #cnt += meguru_nibutan(l,b,l[a]-l[b]) - b
            cnt += bisect.bisect_left(l,l[a]+l[b]) - 1 - b
    print(cnt)

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

K, S = map(int, input().split())
X = []
Y = []
Z = []
count = 0

for i in range(0, K + 1):
	X.append(i)
	Y.append(i)
	Z.append(i)

for i in range(0 ,K + 1):
	for j in range(0 ,K + 1):
		for k in range(0 ,K + 1):
			if S == X[i] + Y[j] + Z[k]:
				count += 1

print(str(count))

### FIXED CODE ###

K, S = map(int, input().split())
count = 0

for i in range(0 ,K + 1):
	for j in range(0 ,K + 1):
		z = S - i - j
		if z >= 0 and z <= K:
			count += 1

print(str(count))
### BUGGY CODE ###

n,m = map(int,input().split())
ans = 0

if n >= m//2:
    ans = m//2
else:
    while n <= m//2:
        n += 1
        m -= 2
    else:
        ans = n-1

print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
ans = 0

if n >= m//2:
    ans = m//2
else:
    ans = n + (m//2-n)//2

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def cmb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

n, k = map(int, input().split())
sortedList = sorted(list(map(int, input().split())))

mod = 10 ** 9 + 7
result = 0
for i in range(1, n - k + 2):
  val = cmb(n - i, k - 1) * (sortedList[n - i] - sortedList[i - 1]) % mod
  result = (result + val) % mod
print(result)


### FIXED CODE ###

n, k = map(int, input().split())
sortedList = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7

factorial = [1]
for i in range(1, n + 1):
  factorial.append((factorial[i - 1] * i) % mod)

def cmb(n, k):
  return factorial[n] * pow(factorial[n - k], mod - 2, mod) * pow(factorial[k], mod - 2, mod)

result = 0
for i in range(1, n - k + 2):
  val = cmb(n - i, k - 1) * (sortedList[n - i] - sortedList[i - 1])
  result += val
print(result % mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
MOD = 10**9 + 7
kake = 0

for i in range(N):
    kake = A[i]
    tasu = 0
    for j in range(i+1, N):
        tasu += A[j]
    ans = (ans + kake*tasu)%MOD
        
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) + [0]
B = [0]*(N+1)

for i in range(N-1):
    B[N-i-1] = A[N-i-1]+B[N-i]
ans = 0
MOD = 10**9 + 7

for i in range(N-1):
    ans = (ans + A[i]*B[i+1])%MOD
        
print(ans)
### BUGGY CODE ###

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

h, w = map(int, input().split())
used = [[False] * (w+2) for _ in range(h+2)]
for r in range(h+2):
    used[r][0] = True
    used[r][-1] = True
for c in range(w+2):
    used[0][c] = True
    used[-1][c] = True
que = deque([])
for r in range(h):
    line = input()
    for c in range(w):
        if line[c] == "#":
            que.append((r+1, c+1, 0))
            used[r+1][c+1] = 0
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while que:
    r, c, k = que.popleft()
    for dr, dc in neighbors:
        nr, nc = r+dr, c+dc
        if not used[nr][nc]:
            que.append((nr, nc, k+1))
            used[nr][nc] = True
print(k)


### FIXED CODE ###

from collections import deque

def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

import numpy as np

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

# 奇数がプラス、偶数がマイナス
cost1 = 0
cum = arr.cumsum()
for i in range(n):
    tmp = abs(cum[i]) + 1
    if i%2==1 and cum[i]<=0: cost1 += tmp ; cum[i:] += tmp
    if i%2==0 and cum[i]>=0: cost1 += tmp ; cum[i:] -= tmp

# 奇数がマイナス、偶数がプラス
cost2 = 0
cum = arr.cumsum()
for i in range(n):
    tmp = abs(cum[i]) + 1
    if i%2==1 and cum[i]>=0: cost2 += tmp ; cum[i:] -= tmp
    if i%2==0 and cum[i]<=0: cost2 += tmp ; cum[i:] += tmp

ans = min(cost1, cost2)
print(ans)



### FIXED CODE ###

import numpy as np

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

# 奇数がプラス、偶数がマイナス
cost1 = 0
cum = 0
for i in range(n):
    cum += arr[i]
    tmp = abs(cum) + 1
    if i%2==1 and cum<=0: cost1 += tmp ; cum += tmp
    if i%2==0 and cum>=0: cost1 += tmp ; cum -= tmp

# 奇数がマイナス、偶数がプラス
cost2 = 0
cum = 0
for i in range(n):
    cum += arr[i]
    tmp = abs(cum) + 1
    if i%2==1 and cum>=0: cost2 += tmp ; cum -= tmp
    if i%2==0 and cum<=0: cost2 += tmp ; cum += tmp


ans = min(cost1, cost2)
print(ans)
### BUGGY CODE ###

N = int(input())
c = list(map(int, input().split()))
c.sort(reverse = True)
mod = 10 ** 9 + 7
tmp = 2 ** (N - 1)
d = tmp // 2
ans = 0
for ci in c:
    ans += ci * tmp
    ans %= mod
    tmp += d
print((ans * 2 ** N) % mod)


### FIXED CODE ###

N = int(input())
c = list(map(int, input().split()))
c.sort(reverse = True)
mod = 10 ** 9 + 7
tmp = (2 ** (N - 1)) % mod
d  = (2 ** (N - 2)) % mod
ans = 0
for ci in c:
    ans += (ci * tmp) % mod
    ans %= mod
    tmp = (tmp + d) % mod
print((ans * 2 ** N) % mod)
### BUGGY CODE ###

N = int(input())
ans = 0

for i in range(1, N):
    ans += i

print(ans)

### FIXED CODE ###

N = int(input())
print((N * (N - 1)) // 2)
### BUGGY CODE ###

n = int(input())
lens = list(map(int,input().split()))
items = list(set(lens))
items.sort(reverse = True)

cnt = 0
for j in items:
  k = lens.count(j)
  if k >= 4 and cnt == 0:
    print(j**2)
    break
  elif k >= 2 and cnt == 0:
    cnt = j
  elif k >= 2 and cnt != 0:
    print(cnt * j)
    break
else:
  print(0)

### FIXED CODE ###

import collections
 
n = int(input())
lens = list(map(int,input().split()))
lens = collections.Counter(lens)
lens = sorted(lens.items(), key=lambda x:x[0], reverse = True)
cnt = 0
for j in lens:
  if j[1] >= 4 and cnt == 0:
    print(j[0]**2)
    break
  elif j[1] >= 2 and cnt == 0:
    cnt = j[0]
  elif j[1] >= 2 and cnt != 0:
    print(cnt * j[0])
    break
else:
    print(0)
### BUGGY CODE ###

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

ans_list = [0]*N
ans_list[1] = abs(cost[0] - cost[1])
temp = 10 **10

for i in range(2,N):
    temp = 10**10
    for j in range(1,K+1):
        if i-j >=0:
            compare = ans_list[i-j] + abs(cost[i-j]-cost[i])
            temp = min(compare, temp)
        else:
            break
    ans_list[i] = temp
print(ans_list.pop())


### FIXED CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

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

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])

### FIXED CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = [[[0] * Z for i in range(Y)] for i in range(X)]
sum_array = []
candidate_array = []

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

candidate_array = [[X - 1, Y - 1, Z - 1, max_sum]]

for i in range(K):
    candidate_array = sorted(candidate_array, key=lambda x: -x[3])

    x, y, z, s = candidate_array.pop(0)

    sum_array.append(s)
    if x != 0 and use_array[x - 1][y][z] == 0:
        use_array[x - 1][y][z] = 1
        diff = A_array[x] - A_array[x - 1]
        candidate_array.append([x - 1, y, z, s - diff])

    if y != 0 and use_array[x][y - 1][z] == 0:
        use_array[x][y - 1][z] = 1
        diff = B_array[y] - B_array[y - 1]
        candidate_array.append([x, y - 1, z, s - diff])

    if z != 0 and use_array[x][y][z - 1] == 0:
        use_array[x][y][z - 1] = 1
        diff = C_array[z] - C_array[z - 1]
        candidate_array.append([x, y, z - 1, s - diff])

for ans in sum_array:
    print(ans)

### FIXED CODE ###

import heapq
X, Y, Z, K = map(int, input().split())
A_array = list(map(int, input().split()))
B_array = list(map(int, input().split()))
C_array = list(map(int, input().split()))

A_array.sort()
B_array.sort()
C_array.sort()

use_array = []
sum_array = []

candidate = []
heapq.heapify(candidate)

max_sum = A_array[-1] + B_array[-1] + C_array[-1]

heapq.heappush(candidate, (0, X - 1, Y - 1, Z - 1))
use_array.append((X - 1, Y - 1, Z - 1))

for i in range(K):
    s, x, y, z = heapq.heappop(candidate)

    sum_array.append(s)
    if x != 0 and (x - 1, y, z) not in use_array:
        use_array.append((x - 1, y, z))
        diff = A_array[x] - A_array[x - 1]
        heapq.heappush(candidate, (s + diff, x - 1, y, z))

    if y != 0 and (x, y - 1, z) not in use_array:
        use_array.append((x, y - 1, z))
        diff = B_array[y] - B_array[y - 1]
        heapq.heappush(candidate, (s + diff, x, y - 1, z))

    if z != 0 and (x, y, z - 1) not in use_array:
        use_array.append((x, y, z - 1))
        diff = C_array[z] - C_array[z - 1]
        heapq.heappush(candidate, (s + diff, x, y, z - 1))

for ans in sum_array:
    print(max_sum - ans)
### BUGGY CODE ###

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

#def cost(i,j):
#    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+abs(h[i] - h[j])
            if dp[i] > cst:
                dp[i]=cst

print(dp[n-1])

### FIXED CODE ###

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

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

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

import math
import collections

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

for i in range(N):
    result = 0
    pop = A.pop(i)
    c = collections.Counter(A)
    for k, v in c.items():
        if v > 1:
            result = result + combinations_count(v, 2)
    A.insert(i, pop)
    print(result)

### FIXED CODE ###

import math
import collections
import numpy as np

def combinations_count(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

c = collections.Counter(A)
ans = 0
for v in c.values():
    if v > 1:
        ans += v*(v-1)//2

for i in range(N):
    v = c[A[i]]
    print(ans + (v-1)*(v-2)//2 - v*(v-1)//2)
### BUGGY CODE ###

N = int(input())
A = [i for i in map(int, input().split())]

for i in range(1, N+1):
    print(A.count(i))


### FIXED CODE ###

N = int(input())
l = [0]*N
A = [j for j in map(int, input().split())]

for i in A:
    l[i-1] += 1

print(*l, sep="\n")
### BUGGY CODE ###

N,M = map(int,input().split())
i = N
while M%i != 0:
    i += 1
print(M//i)

### FIXED CODE ###

N,M = map(int,input().split())
divisors = []
for i in range(1,int(M**.5)+1):
    if M%i == 0:
        divisors.append(i)
        if M//i != i:
            divisors.append(M//i)
ans = 1
for x in divisors:
    if x <= M//N:
        ans = max(ans,x)
print(ans)