Harryxun/stf_run huggingface dataset:
def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    cnt = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    visited = [False]*N
    visited[0] = True

    def dfs(v: int):
        nonlocal visited
        nonlocal cnt
        if all(visited):
            return
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            dfs(n)
        return

    dfs(0)
    print(*cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10**9)


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    cnt = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    visited = [False]*N
    visited[0] = True
    q = deque([0])
    while q:
        v = q.pop()
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            q.append(n)
    print(*cnt)


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

for line in sys.stdin:
   try:
      array = [int(x) for x in line.split()]
      array.sort()
      if array[2]**2 == (array[0]**2+array[1]**2):
         print('YES')
      else:
         print('NO')
   except(ValueError):
      continue

### FIXED CODE ###

import sys

for line in sys.stdin:
    try:
        a,b,c = [int(x) for x in line.split()]
        if (a**2+b**2) == c**2:
            print('YES')
        elif (a**2+c**2) == b**2:
            print('YES')
        elif (b**2+c**2) == a**2:
            print('YES')
        else:
            print('NO')
    except(ValueError):
        continue
import numpy as np
import math

def f(x,a):
  return np.array([ c^x for c in a],dtype=np.int64).sum()

def bitlength(x):
  i=0
  while x > 0:
    x //= 2
    i += 1
  return i

def bitlengthceil(x):
  l = bitlength(x)
  if x == 2**l:
    return l
  else:
    return (l+1)

(N,K) = map(int,input().split())
A = np.array(list(map(int,input().split())),dtype=np.int64)
M=40

B = np.empty((M,N),dtype=np.int64)
Y = np.empty(M,dtype=np.int64)
D = np.empty(M,dtype=np.int64)

for n in range(N):
  for m in range(M):
    B[m,n] = (A[n] >> m) % 2

for m in range(M):
  s = B[m].sum()
  if 2*s < N:
    Y[m] = 1
    D[m] = (N-2*s)<<m
  else:
    Y[m] = 0
    D[m] = 0

#print(Y[0])

#k = math.floor(math.log2(K))
k = bitlength(K)
X = np.array([Y[m]<<m for m in range(k+1)]).sum()
#print(X)
if X <= K:
  print(f(X,A))
else:
  d = X - K
#  print("d=",d)
#  p = math.ceil(math.log2(d))
  p = bitlengthceil(d)-1
#  print("p=",p)
#  w = np.array([Y[m]<<m for m in range(p)]).sum()
  ans=0
  for m in range(p,k+1):
    if Y[m] == 1:
      ans = max(ans,f(X^(Y[m]<<m),A))

  for m in range(p-1,-1,-1):
    if Y[m] == 0:
      continue
    elif Y[m]<<(m+1) < d:
      break
    elif Y[m]<<m < d:
      X = X^(Y[m]<<m)
      continue
    else:
#      print(X,m)
      ans = max(ans,f(X^(Y[m]<<m),A))
  print(ans)

### FIXED CODE ###

inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()

L = K+1
M = len(bin(L))-2
MM = max(M, len(bin(max(A)))-2)
best = []
ones_num = []
zeros_num = []
for m in range(MM):
    ones = sum([ (A[i]>>m)&1 for i in range(N) ])
    zeros = N - ones
    ones_num.append(ones)
    zeros_num.append(zeros)
    if ones >= zeros:
        best.append(0)
    else:
        best.append(1)
cur = sum([ (N-ones_num[m] if (best[m] and m < M-1) else ones_num[m])<<m for m in range(MM)])
ans = cur
m = M - 1
while m > 0:
    cur += (zeros_num[m]-ones_num[m])<<m
    m -= 1
    while (L >> m)&1 == 0:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        m -= 1
        if m < 0:
            break
    else:
        if best[m] == 1:
            cur += (ones_num[m]-zeros_num[m])<<m
        if cur > ans:
            ans = cur
print(ans)
N, M, X = map(int, input().split())
#
C = []
A = []
for i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])

# N, M, X = 3, 3, 10
# C = [60,70,50]
# A = [[2,2,4],[8,7,9],[2,3,9]]

alist = []

for i in range(1 << N):
    mlist = []
    slist = []
    plist = [0] * M # 0要素の数M個のリスト

    for j in range(N):

        if (i >> j) & 1 == 1:
            mlist.append(C[j])
            slist.append(A[j])
    # print(i,mlist,slist,len(slist))

    for j in range(len(slist)):
        if len(slist)==1:
            plist = slist[j]
        else:
            plist = [a + b for a, b in zip(plist, slist[j])]

    if all((x >= X for x in plist)) == True:
        alist.append(sum(mlist))
        # print(i,plist)

print(min(alist))


### FIXED CODE ###

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

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

alist = []

for i in range(1 << N):
    mlist = []
    slist = []
    plist = [0] * M # 0要素の数M個のリスト

    for j in range(N):

        if (i >> j) & 1 == 1:
            mlist.append(C[j])
            slist.append(A[j])

    for j in range(len(slist)):
        if len(slist)==1:
            plist = slist[j]
        else:
            plist = [a + b for a, b in zip(plist, slist[j])]

    if all((x >= X for x in plist)) == True:
        alist.append(sum(mlist))

if len(alist) != 0:
    print(min(alist))
else:
    print(-1)
S = input()
ans = 0 
ans_lis = [0]

for i in range(len(S)):
    if S[i] in ACGT:
        ans = ans + 1 
        if i == (len(S)-1):
            ans_lis.append(ans)
    else:
        ans_lis.append(ans)
        ans = 0 

print(max(ans_lis))

### FIXED CODE ###

S = input()
ACGT = ["A","C","G","T"]

ans = 0 
ans_lis = [0]

for i in range(len(S)):
    if S[i] in ACGT:
        ans = ans + 1 
        if i == (len(S)-1):
            ans_lis.append(ans)
    elif S[i] not in ACGT:
        ans_lis.append(ans)
        ans = 0 

print(max(ans_lis))
import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
s = [input() for _ in range(n)]
s.sort()
ss = list(set(s))
ss.sort()
a = [0]*len(ss)
i = 0
while n-1 > i:
    if s[i] == s[i+1]:
        a[ss.index(s[i])] += 1
        i += 1
    else:
        i += 1
m = max(a)
for k in range(len(a)):
    if a[k] == m:
        print(ss[k])


### FIXED CODE ###

import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
a = intl()
a = list(set(a))
if len(a) == 2:
    print("Yes")
else:
    print("No")
# -*- coding utf-8 -*-

n = int(input())
k = int(input())
x = int(input())
y = int(input())

if n <= k :
    print(n*x)
elif k < n :
    ans = (k*x) + (y*(n-k))
    print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-

a = int(input())
b = int(input())
h = int(input())

x = (a+b)*h/2

print(round(x))
for n in range(0,20):
    if n*a-n>=b-1:
        break

print(n)

### FIXED CODE ###

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

for n in range(0,20):
    if n*(a-1)>=b-1:
        break

print(n)
import sys
from math import factorial

N, M = (int(s) for s in sys.stdin.split(' '))

total = 0
if N > 1:
  total += factorial(N) / factorial(N - 2) / 2
if M > 1:
  total += factorial(M) / factorial(M - 2) / 2
  
print(total)

### FIXED CODE ###

import sys
from math import factorial

line = input()
N, M = (int(s) for s in line.split(' '))

total = 0
if N > 1:
  total += factorial(N) / factorial(N - 2) / 2
if M > 1:
  total += factorial(M) / factorial(M - 2) / 2

print(int(total))
#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    from scipy.optimize import dual_annealing
    A = [a-i for i, a in enumerate(A, 1)]
    def f(b):
        return sum(abs(a-b) for a in A)
    res = dual_annealing(f, [[min(A), max(A)]], maxiter=500)
    # print(res)
    b = res.x[0]
    return min(f(int(round(b))), f(int(round(b+1))))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"    
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    A = sorted(a - i for i, a in enumerate(A))
    m = A[N//2]
    return sum(abs(a-m) for a in A)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()
BingoRow = 3
BingoList = [list(map(int,input().split())) for i in range(BingoRow)]

TargetRow = int(input())
TargetList = [int(input()) for i in range(TargetRow)]

ansList = []
x = 0
flg = false
for row in BingoList:
  for num in row:
    flg = false
    for target in TargetList:
      if num == target:
        ansList.append(1)
        flg = true
    if !flg:
      ansList.append(0)

if (ansList[0] + ansList[1] + ansList[2]) == 3:
  print('Yes')
elif (ansList[3] + ansList[4] + ansList[5]) == 3:
  print('Yes')
elif (ansList[6] + ansList[7] + ansList[8]) == 3:
  print('Yes')
elif (ansList[0] + ansList[3] + ansList[6]) == 3:
  print('Yes')
elif (ansList[1] + ansList[4] + ansList[7]) == 3:
  print('Yes')
elif (ansList[2] + ansList[5] + ansList[8]) == 3:
  print('Yes')
elif (ansList[0] + ansList[4] + ansList[8]) == 3:
  print('Yes')
elif (ansList[2] + ansList[4] + ansList[6]) == 3:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

BingoRow = 3
BingoList = [list(map(int,input().split())) for i in range(BingoRow)]
 
TargetRow = int(input())
TargetList = [int(input()) for i in range(TargetRow)]
 
ansList = []
x = 0
flg = False
for row in BingoList:
  for num in row:
    flg = False
    for target in TargetList:
      if num == target:
        ansList.append(1)
        flg = True
    if not flg:
      ansList.append(0)
 
if (ansList[0] + ansList[1] + ansList[2]) == 3:
  print('Yes')
elif (ansList[3] + ansList[4] + ansList[5]) == 3:
  print('Yes')
elif (ansList[6] + ansList[7] + ansList[8]) == 3:
  print('Yes')
elif (ansList[0] + ansList[3] + ansList[6]) == 3:
  print('Yes')
elif (ansList[1] + ansList[4] + ansList[7]) == 3:
  print('Yes')
elif (ansList[2] + ansList[5] + ansList[8]) == 3:
  print('Yes')
elif (ansList[0] + ansList[4] + ansList[8]) == 3:
  print('Yes')
elif (ansList[2] + ansList[4] + ansList[6]) == 3:
  print('Yes')
else:
  print('No')
H, W = map(int, input().split())

List = list(range(W))
count = 0

for i in range(W):
    if List[i]%2 == 0:
      count +=1

if W%2 ==0:
  Answer = count*H
else:
  if H%2 ==0:
    Answer = count*H - H/2
  else:
    Answer = count*(H-1) - (H-1)/2 + count

print(int(Answer))


### FIXED CODE ###

H, W = map(int, input().split())

if H==1 or W==1:
  Answer =1

elif W%2 ==0:
  Answer = W/2*H
  
else:
  count = (W-1)/2 +1
  if H%2 ==0:
    Answer = count*H - H/2
  else:
    Answer = count*H - (H-1)/2

print(int(Answer))
n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    max = 0

    while True:
        i = 0
        max += l[i]
        if max < x:
            ans += 1
        i += 1
    print(ans)

### FIXED CODE ###

def main():
    n,x = map(int, input().split())
    l = list(map(int, input().split()))
    ans = 1
    max = 0

    #while True:
        #i = 0
        #max += l[i]
        #if max < x:
            #ans += 1
        #i += 1

    for i in range(len(l)):
        max += l[i]
        if max <= x:
            ans += 1
    print(ans)

main()
import sys

N = int(input())
G = [[] for i in range(N)]
temp = sys.stdin.readlines()
for line in temp:
    u, v, d = map(int, line.split())
    G[u-1].append([v-1, d])
    G[v-1].append([u-1, d])
    
def dfs(v, G, cur=0):
    # 色をメモ
    color[v] = cur
        
    # 隣接するノードの色を調べる
    for next_v in G[v]:
        # 隣接ノードが探索済みなら、色が正しいか確かめる
        if color[next_v[0]] != -1:
            continue
            
        # 隣接ノードが未探索なら、正しい色に更新して再帰的に探索
        if next_v[1] % 2 == 0:
            dfs(next_v[0], G, cur)
        else:
            dfs(next_v[0], G, 1-cur)

color = [-1 for i in range(N)]
dfs(0, G)
for i in range(N):
    print(color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
temp = sys.stdin.readlines()
for line in temp:
    u, v, d = map(int, line.split())
    G[u-1].append([v-1, d])
    G[v-1].append([u-1, d])
    
def dfs(v, G, cur=0):
    # 色をメモ
    color[v] = cur
        
    # 隣接するノードの色を調べる
    for next_v in G[v]:
        # 隣接ノードが探索済みなら、色が正しいか確かめる
        if color[next_v[0]] != -1:
            continue
            
        # 隣接ノードが未探索なら、正しい色に更新して再帰的に探索
        if next_v[1] % 2 == 0:
            dfs(next_v[0], G, cur)
        else:
            dfs(next_v[0], G, 1-cur)

color = [-1 for i in range(N)]
dfs(0, G)
for i in range(N):
    print(color[i])
H,W = map(int, input().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)

print(2)



### FIXED CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)
#include<iostream>
using namespace std;
int main(){
    long int n;
    cin>>n;
    long int a=0,w=0,r=0,t=0;
    while(n--){
        string s;
        cin>>s;
        if(s=="AC")
        a+=1;
        else if(s=="WA")
        w+=1;
        else if(s=="TLE")
        t+=1;
        else
        r+=1;
    }
    cout<<"AC "<<"* "<<a<<endl;
    cout<<"WA "<<"* "<<w<<endl;
    cout<<"TLE "<<"* "<<t<<endl;
    cout<<"RA "<<"* "<<r<<endl;
    return 0;
}


### FIXED CODE ###

# cook your dish here
n=int(input())
if n%1000==0 :
    print(0)
else :
    print(1000-(n%1000))
import math

def isprime(number):
    for i in range(2, number):
        if number % i == 0:
            return False
    return True

A, B = map(int, input().split())
count = 1

if B < A:
    C = B
    B = A
    A = C
# A <= B

for i in range(2, round(A / 2 + 1):
    if A % i == 0:
        if B % i == 0:
            if isprime(i):
                count += 1

print(str(count))


### FIXED CODE ###

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)
N,X,M = map(int,input().split())
A = [100001]*(2*(10**5)+100)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
  
if i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)




### FIXED CODE ###

N,X,M = map(int,input().split())
A = [100001]*(2*(10**5)+100)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
if N == 1:
  print(X)
  exit()
elif i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(n)]
a=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
import math
import functools


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

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)
result = 0
mod = lcm_list(a)-1

for i in range(len(a)):
    result += mod % a[i] 

print(result)

### FIXED CODE ###

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

print(sum(a) - n)
L = []
for _ in range(5):
    n = int(input())
    L.append([n%10, n])

L.sort()
for i in range(5):
    if L[i][0] != 0:
        la = L[i][1]
        l = i
        break

tot = 0
for i in range(5):
    if i != l:
        if L[i][1] % 10 != 0:
            k = L[i][1]//10 + 1
        else:
            k = L[i][1]//10
        tot += k*10
tot += la
print(tot)


### FIXED CODE ###

tot = 0
m = 0
for i in range(5):
    s = int(input())
    if s % 10 == 0:
        rem = 0
    else:
        rem = s%10 - 10
        s = 10*(s//10 + 1)
    m = min(m, rem)
    tot += s

print(tot+m)
n,t = map(int,input().split())
ct = [list(map(int,input().split())) for i in range(n)]
C = []
T1 = []

for i in range(n):
  C.append(ct[i][0])
  T1.append(ct[i][1])

if min(T1) >= t:
  print("TLE")

for i in range(n):
  mc = min(C)
  if ct[C.index(min(C))][1] >= t:
    C.remove(min(C))
    ct.remove(ct[C.index(min(C))])
  else:
    break
    
print(min(C))

### FIXED CODE ###

n,t = map(int,input().split())
ct = [list(map(int,input().split())) for i in range(n)]
T = []

for h in range(n):
  T.append(ct[h][1])
  
if min(T) > t:
  print("TLE")
  exit()
else:
  for j in range(n):
    if ct[j][1] <= t:
      c = ct[j][0]
      k = j
      break
 

for i in range(k+1,n):
  if ct[i][1] <= t:
    c = min(c,ct[i][0])
    
print(c)
N = int(input())
a = list( map( int, input().split()))
a = sorted(a)
Alice = 0
Bob = 0

for i in range(N):
	Alice += int(a[2*i])  
	Bob += int(a[2*i + 1])
    
print(Alice -Bob)

### FIXED CODE ###

N = int(input())
a = list( map( int, input().split()))
a = sorted(a)
a.reverse()
Alice = 0
Bob = 0
a.append(0)
a.append(0)

for i in range(N//2 + 1):
	Alice += int(a[2 * i])  
	Bob += int(a[2 * i + 1])
    
print(Alice -Bob)
import heapq
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

li=[]
push=heapq.heappush
pop=heapq.heappop

push(li,(-a[0]-b[0]-c[0],0,0,0))
ans=[]
used=set()

for _ in range(k):
    value,i,j,l=pop(li)
    ans.append(-value)
    if i<x-1 and (i+1,j,l) not in used:
        push(li,(-a[i+1]-b[j]-c[l],i+i,j,l))
        used.add((i+1,j,l))
    if j<y-1 and (i,j+1,l) not in used:
        push(li,(-a[i]-b[j+1]-c[l],i,j+1,l))
        used.add((i,j+1,l))
    if k<z-1 and (i,j,l+1) not in used:
        push(li,(-a[i]-b[j]-c[l+1],i,j,l+1))
        used.add((i,j,l+1))
for i in ans:
    print(i)

### FIXED CODE ###

import heapq
x,y,z,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

li=[]
push=heapq.heappush
pop=heapq.heappop

push(li,(-a[0]-b[0]-c[0],0,0,0))
ans=[]
used=set()

for _ in range(k):
    value,i,j,l=pop(li)
    ans.append(-value)
    if i<x-1 and (i+1,j,l) not in used:
        push(li,(-a[i+1]-b[j]-c[l],i+1,j,l))
        used.add((i+1,j,l))
    if j<y-1 and (i,j+1,l) not in used:
        push(li,(-a[i]-b[j+1]-c[l],i,j+1,l))
        used.add((i,j+1,l))
    if l<z-1 and (i,j,l+1) not in used:
        push(li,(-a[i]-b[j]-c[l+1],i,j,l+1))
        used.add((i,j,l+1))
for i in ans:
    print(i)
n=int(input())
if n%2=0:
  print(n//2)
else:
  print(n//2+1)

### FIXED CODE ###

n=int(input())
if n%2==0:
  print(n//2)
else:
  print(n//2+1)
def acinput():
    return list(map(int,input().split(" ")))


N,M=acinput()
a=[0]*(N+1)
for i in range(M):
    a[int(input())]=1


Mod=1000000007

def solve(x):
    global dp,M
    if dp[x]>=0:
        return dp[x]

    if x<0:
        return 0

    res=0
    zeroflg=True
    if  a[x-1]!=1:
        res+=solve(x-1)%Mod
        zeroflg=False
    if a[x-2]!=1:
        res+=solve(x-2)%Mod
        zeroflg=False
    
    if zeroflg:
        return 0
    dp[x]=res
    return res

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

print(solve(N)%Mod)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def acinput():
    return list(map(int, input().split(" ")))


N, M = acinput()
a = [0]*(N+1)
for i in range(M):
    a[int(input())] = 1


Mod = 1000000007


def solve(x):
    global dp, Mod
    if dp[x] >= 0:
        return dp[x]

    if x < 0:
        return 0

    res = 0
    zeroflg = True

    if  a[x-2] != 1:
        res += solve(x-2) 
        zeroflg = False

    if a[x-1] != 1:
        res += solve(x-1)
        zeroflg = False

    if zeroflg:
        return 0
    dp[x] = res% Mod
    return res


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

print(solve(N) % Mod)


'''
5 1
1
'''