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

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

# coding: utf-8
# Your code here!
n,H=map(int,input().split())
S=[]
for i in range(n):
    
    S.append(list(map(int,input().split())))
    
a=[]
b=[]
for i in range(n):
    a.append(S[i][0])
    
for i in range(n):
    if(max(a)<S[i][1]):
        b.append(S[i][1])

b.sort()
b.reverse()
k=0
count=0
while H>0:
    if len(b)>k:
        H-=b[k]
        k+=1
        count+=1
    else:
        
        count+=H//max(a)
        if(H%max(a)!=0):
            count+=1
        H=0

print(count)


### FIXED CODE ###

# coding: utf-8
# Your code here!
n,H=map(int,input().split())
S=[]
for i in range(n):
    
    S.append(list(map(int,input().split())))
    
a=[]
b=[]
for i in range(n):
    a.append(S[i][0])

maxa=max(a)    
for i in range(n):
    if(maxa<S[i][1]):
        b.append(S[i][1])

b.sort()
b.reverse()
k=0
count=0
lenb=len(b)
while H>0:
    if lenb>k:
        H-=b[k]
        k+=1
        count+=1
    else:
        
        count+=H//maxa
        if(H%maxa!=0):
            count+=1
        H=0

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

n = int(input())
a = list(map(int, input().split()))
import numpy as np
na = np.array(a).cumsum()
cnt = 0
if(na[0] > 0):
  for i in range(n):
    delta = abs(na[i]) + 1
    if(i % 2 == 0 and na[i] <= 0):
      cnt = cnt + delta
      for j in range(i, n):
        na[j] += delta 
    elif(i % 2 == 1 and na[i] >= 0):
      cnt = cnt + delta
      for j in range(i, n):
        na[j] -= delta
    else:
      na[i]
else:
  for i in range(n):
    delta = abs(na[i]) + 1
    if(i % 2 == 1 and na[i] <= 0):
      cnt = cnt + delta
      for j in range(i, n):
        na[j] += delta
    elif(i % 2 == 0 and na[i] >= 0):
      cnt = cnt + delta
      for j in range(i, n):
        na[j] -= delta
    else:
      na[i]
print(cnt)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import numpy as np
na1 = np.array(a).cumsum()
na2 = np.array(a).cumsum()
cnt1 = 0
hoge1 = 0
cnt2 = 0
hoge2 = 0
delta1 = 0
delta2 = 0
for i in range(n):
  na1[i] += hoge1
  na2[i] += hoge2
  if(i % 2 == 0 and na1[i] <= 0):
    delta1 = abs(na1[i]) + 1
    cnt1 = cnt1 + delta1
    hoge1 += delta1
    na1[i] += delta1
  elif(i % 2 == 1 and na1[i] >= 0):
    delta1 = abs(na1[i]) + 1 
    cnt1 = cnt1 + delta1
    hoge1 -= delta1
    na1[i] -= delta1    
  if(i % 2 == 1 and na2[i] <= 0):
    delta2 = abs(na2[i]) + 1
    cnt2 = cnt2 + delta2
    hoge2 += delta2
    na2[i] += delta2  
  elif(i % 2 == 0 and na2[i] >= 0):
    delta2 = abs(na2[i]) + 1
    cnt2 = cnt2 + delta2
    hoge2 -= delta2
    na2[i] -= delta2
  else:
    na1[i]
print(min([abs(cnt1),abs(cnt2)]))
### BUGGY CODE ###

h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0]*h
res2=[0]*w
for i in range(m):
    bomb1=bomb[i]
    res1[bomb1[0]-1]+=1
    res2[bomb1[1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=[]
for j in range(h):
    res3=res1[j]
    if res3>s1:
            l1=[j+1]
            s1=res3
    elif res3==s1:
            l1.append(j+1)
s2=0
l2=[]
for k in range(w):
    res4=res2[k]
    if res4>s2:
            l2=[k+1]
            s2=res4
    elif res4==s2:
            l2.append(k+1)
count=0
for l in range(m):
    bomb2=bomb[l]
    if bomb2[0] in l1 and bomb2[1] in l2:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)


### FIXED CODE ###

from collections import deque

h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0]*h
res2=[0]*w
for i in range(m):
    bomb1=bomb[i]
    res1[bomb1[0]-1]+=1
    res2[bomb1[1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=deque()
for j in range(h):
    res3=res1[j]
    if res3>s1:
            l1=[j+1]
            s1=res3
    elif res3==s1:
            l1.append(j+1)
s2=0
l2=deque()
for k in range(w):
    res4=res2[k]
    if res4>s2:
            l2=[k+1]
            s2=res4
    elif res4==s2:
            l2.append(k+1)
l3=set(l1)
l4=set(l2)
count=0

for l in range(m):
    bomb2=bomb[l]
    if bomb2[0] in l3 and bomb2[1] in l4:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

N = int(input())
sequence = list(map(int,input().split()))
ans = []
for i in range(N):
    a_i = sequence[i]
    ans.append(a_i)
    ans = ans[::-1]
print(" ".join([str(i) for i in ans]))


### FIXED CODE ###

"""TLE
N = int(input())
sequence = list(input().split())
ans = []
for i in range(N):
    a_i = sequence[i]
    ans.append(a_i)
    ans = ans[::-1]
print(" ".join(ans))
"""

from collections import deque
n = int(input())
sequence = deque(map(int,input().split()))
ans = deque()
if n % 2 == 1:
    for i in range(n):
        if i % 2 == 0:
            ans.appendleft(sequence[0])
        else:
            ans.append(sequence[0])
        sequence.popleft()
        #print(ans)
else:
    for i in range(n):
        if i % 2 == 1:
            ans.appendleft(sequence[0])
        else:
            ans.append(sequence[0])
        sequence.popleft()
        #print(ans)
print(*ans)
### BUGGY CODE ###

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

A_list=[]
B_list=[]
for i in range(N):
    A, B = map(int,input().split())
    A_list.append(A)
    B_list.append(B)

cost = 0
total_num = 0
num = 0
while True:
    index = A_list.index(min(A_list))
    num = B_list[index]
    if M > num:
        total_num += num
        cost += min(A_list)*num
        A_list.pop(index)
        B_list.pop(index)
        M -= num
    else:
        cost += min(A_list)*M
        break

print(cost)

### FIXED CODE ###

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

AB_list=[]

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

AB_list = sorted(AB_list)
cost = 0
num = 0
for AB in AB_list:
    num = AB[1]
    if M > num:
        cost += AB[0]*num
        M -= num
    else:
        cost += AB[0]*M
        break

print(cost)
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    # (1) Si≠Sj & Sj≠Sk & Sk≠Si ← すべて違う文字(RGBを網羅している)ということ
    # (2) j-i≠k-j ← 等間隔でないということ 

    R = []
    G = []
    B = []
    for idx, s in enumerate(S):
        if s == "R":
            R.append(idx)
        elif s == "G":
            G.append(idx)
        else:
            B.append(idx)
    
    total = 0
    for r in R:
        for g in G:
            for b in B:
                rgb = sorted([r, g, b])
                total += rgb[1] - rgb[0] != rgb[2] - rgb[1]
    
    print(total)

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    # (1) Si≠Sj & Sj≠Sk & Sk≠Si ← すべて違う文字(RGBを網羅している)ということ
    # (2) j-i≠k-j ← 等間隔でないということ 

    R = 0
    G = 0
    B = 0
    for s in S:
        if s == "R":
            R += 1
        elif s == "G":
            G += 1
        else:
            B += 1    
    total = R*G*B

    # 条件に合わない件数をカウント
    for i in range(N-2):
        for j in range(i+1, N-1):
            # 文字の位置が等間隔の場合をチェック
            k = j + (j-i)
            # カウントしないケースは以下の通り
            # (1) チェック対象の3文字目の位置がNを超える
            # (2) 同じ文字が含まれる場合 ← すでに除外済み
            if k >= N or S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
                continue
            
            total -= 1
    
    print(total)
### BUGGY CODE ###

def main():
    import queue
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = queue.Queue()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.put([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        q_ = queue.Queue()
        for _ in range(q.qsize()):
            b = q.get()
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.put([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.put([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.put([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.put([b[0],b[1]+1])
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

import bisect
import sys
import heapq
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
sort_by_y = sorted([[j, i] for i,j in city_ls], key=lambda x:x[0])
G = []
id2pos = {i : tuple(j) for i, j in enumerate(city_ls)}
pos2id = {j : i for i, j in id2pos.items()}
for i in range(len(sort_by_x)-1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
sort_by_x.sort(key=lambda x:x[1])
for i in range(len(sort_by_x) - 1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[1] - next_by_x[1]), current_by_x, next_by_x))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in G:
    (cost, _from, _to) = i
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)

### FIXED CODE ###

import sys
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
G = []
pos2id = {tuple(j) : i for i, j in enumerate(city_ls)}
for i in range(len(sort_by_x)-1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
sort_by_x.sort(key=lambda x:x[1])
for i in range(len(sort_by_x) - 1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[1] - next_by_x[1]), current_by_x, next_by_x))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in G:
    (cost, _from, _to) = i
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)
### BUGGY CODE ###

N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]
mod = pow(10,9) + 7

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

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if j not in a:
      dp[j] += dp[i]
      dp[j] %= mod
      
print(dp[N])

### FIXED CODE ###

N, M = map(int,input().split())
a = [int(input()) for _ in range(M)]
mod = pow(10,9) + 7

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

ok = [True]*(N+1)
for i in a:
  ok[i] = False

for i in range(N):
  for j in range(i+1,min(N+1,i+3)):
    if ok[j]:
      dp[j] += dp[i]
      dp[j] %= mod
      
print(dp[N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

tree = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

checked = [False for _ in range(N+1)]
def dig(i,tmp):
    global checked
    tmp += adds[i]
    ans[i] = tmp
    checked[i] = True
    for v in tree[i]:
	    if not checked[v]: dig(v,tmp)

tmp = 0
dig(1,tmp)

print(' '.join(str(ans[i]) for i in range(1,N+1)))

### FIXED CODE ###

from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = {i+1:0 for i in range(N)}
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))
### BUGGY CODE ###

n = int(input())
for x in range(1, 3501):
  for y in range(1, 3501):
    t = 4 * x * y - n * y - n * x
    if(t <= 0):
      continue
    if((n * x * y) % t == 0):
      print(x, y, (n * x * y) // t)
      exit(0)

### FIXED CODE ###

n = int(input())
for x in range(1, 3501):
  for y in range(1, 3501):
    t = 4 * x * y - n * y - n * x
    if(t <= 0):
      continue
    if((n * x * y) % t == 0):
      print(x, y, (n * x * y) // t)
      exit(0)
### BUGGY CODE ###

n=int(input())
s=list(input())
q=int(input())
k=list(map(int,input().split()))
for i in range(q):
    p=s[:]
    h=0
    while p.count("D")!=0:
        f=p.index("D")
        p=p[f+1:]
        a=0
        m=(k[i]-1 if len(p)>=k[i]-1 else len(p))
        for c in range(m):
            if p[c]=="M":
                a+=1
            elif p[c]=="C":
                h+=a
    else:
        print(h)            

### FIXED CODE ###

n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
    temp = 0
    for j in range(i,N):
        temp += A[j]
        if temp%K == j-i+1:
            cnt += 1
            
print (cnt)

### FIXED CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for i in range(N+1)]
for i in range(1,N+1):
    S[i] = S[i-1] + A[i-1]
cnt = 0
dict1 = {}
        
dict1[0] = 1

for j in range(1,N+1):
    if j-K >= 0:
        dict1[(S[j-K]-j+K)%K] -= 1
    if (S[j]-j)%K in dict1:
        cnt += dict1[(S[j]-j)%K]
        dict1[(S[j]-j)%K] += 1
    else:
        dict1[(S[j]-j)%K] = 1
print (cnt)
### BUGGY CODE ###

def main():
  n = int(input())
  S = input()
  q = int(input())
  K = list(map(int, input().split()))
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for i,s in enumerate(S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      end = i - k + 1
      if end >= 0:
        e = S[end]
        if e == "D":
          d -= 1
          dm -= m
        elif e == "M":
          m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  S = input()[:-1]
  q = int(input())
  K = map(int, input().split())
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

N = int(input())
S = input()

from itertools import permutations, combinations,combinations_with_replacement,product
L = list(combinations(range(N), 3))   #nCr
A=[]
for i in L:
  A.append(S[i[0]]+S[i[1]]+S[i[2]])
print(len(set(A)))

### FIXED CODE ###

N = int(input())
S = input()
Pin = ['{0:03d}'.format(a) for a in range(0,1000)]
cnt = 0
for i in Pin:
  S1 = S
  A1 = S1.find(i[0])
  if A1!=-1:
    S2 = S1[(A1+1):]
    A2 = S2.find(i[1])
    if A2!=-1:
      S3 = S2[(A2+1):]
      A3 = S3.find(i[2])
      if A3!=-1:
        cnt +=1
print(cnt)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
    rs = list(map(int, input().split()))
    rs = [r-1 for r in rs]
    A.append(rs)

cnts = [0] * n
days = 1
while True:
    tekis = []
    # print("Day",days, cnts)
    fin = 0
    for cnt,a in zip(cnts,A):
        if cnt == n-1: 
            tekis.append(-1)
            fin += 1
        else: 
            tekis.append(a[cnt])
    if fin == n: 
        print(days-1)
        exit()
    # 敵の敵が自分だったらマッチング成立
    flg = False
    matched = [False] * n
    for i,teki in enumerate(tekis):
        if matched[teki] or teki==-1:continue
        if tekis[teki] == i:
            cnts[i] += 1
            matched[i] = True
            cnts[teki] += 1
            matched[teki] = True
            flg = True
            # print("{}vs{}".format(i,teki))
    # if all([cnt == n-1 for cnt in cnts]):
    #     print(days)
    #     exit()  
    if not flg:
        print(-1)
        exit()
    days += 1

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
beauty=[0 for _ in range(x*y*z)]
index=0
for i in range(x):
    for j in range(y):
        for l in range(z):
            beauty[index]=a[i]+b[j]+c[l]
            index+=1
beauty.sort(key=lambda x:-x)
# print(beauty)
for i in range(k):
    print(beauty[i])


### FIXED CODE ###


x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(key=lambda x:-x)
b.sort(key=lambda x:-x)
c.sort(key=lambda x:-x)
beauty=[]
index=0
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1)*(j+1)*(l+1)<=k:
                beauty.append(a[i]+b[j]+c[l])
            else:
                break
beauty.sort(key=lambda x:-x)
for i in range(k):
    print(beauty[i])