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

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        z = z[(len(z)+1)//2:]
        max_z = max(z)
        ans = max(ans, max_z)
    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.permutations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    for ((_, under_y), (_, top_y)) in itertools.permutations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
            
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

import math

n = int(input())
sums = 0
sums += n*(n-1)*3 + 1

for k in range(2,n+1):
    for l in range(2,n+1):
        for p in range(2,n+1):
            sums += math.gcd(math.gcd(k,l),p)

print(sums)

### FIXED CODE ###

import math

n = int(input())
sums = 0
for k in range(1,n+1):
    for l in range(1,n+1):
        a =math.gcd(k,l)
        for p in range(1,n+1):
            sums += math.gcd(a,p)

print(sums)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[0]*(n+1)
ok=[True]*(n+1)
for i in a:
    ok[i]=False

dp[0]=1
mod=10**9+7
for now in range(n):
    for next in range(now+1,min(n+1,now+3)):
        if ok[next]:
            dp[next]+=dp[now]
            dp[next]%mod

print(dp[n]%mod)


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

n = int(input())
S = input()
L = []
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      cnt = 0
      iflag = 0
      jflag = 0
      while True:
        if cnt >= n:
          break
        if iflag == 0 and S[cnt] == str(i):
          iflag = 1
          cnt += 1
          continue
        if iflag == 1 and jflag == 0 and S[cnt] == str(j):
          jflag= 1
          cnt += 1
          continue
        if jflag == 1 and S[cnt] == str(k):
          ans += 1
          break
        cnt += 1

print(ans)

### FIXED CODE ###

n = int(input())
S = input()
L = []
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      cnt = 0
      iflag = 0
      jflag = 0
      while True:
        if cnt >= n:
          break
        if iflag == 0 and S[cnt] == str(i):
          iflag = 1
          cnt += 1
          continue
        if iflag == 1 and jflag == 0 and S[cnt] == str(j):
          jflag= 1
          cnt += 1
          continue
        if jflag == 1 and S[cnt] == str(k):
          ans += 1
          break
        cnt += 1

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

from math import inf
from random import randint,random
import time
START=time.time()
PROB=0.99

def f(a,d,T):
    try:
        return T[d:].index(a)+d
    except ValueError:
        return len(T)

from random import randint
A=26

D=int(input())

C=[0]+list(map(int,input().split())) #減る満足度のベース
S=[0]*(D+1) #S[d][i] :(d+1)日目にコンテストiを開催した時の満足度

for i in range(1,D+1):
    S[i]=[0]+list(map(int,input().split()))
 
def g(d,q,S,C,T):
    p=T[d]

    a=f(p,d+1,T)
    b=f(q,d+1,T)
    
    Y=0
    h=L[d-1][p]
    for i in range(d,a):
        h+=1
        Y+=h-L[i][p]
        
    m=0
    Z=0
    for j in range(d,b):
        Z-=m-L[j][q]
        m+=1
        
    return (S[d][q]-S[d][p])-Z*C[q]+Y*C[p]

T=[0]
L=[[0]*(A+1) for _ in range(D+1)]
for d in range(1,D+1):
    M=-inf
    E=0

    for j in range(1,A+1):
        X=0
        for k in range(1,A+1):
            if j!=k:
                X-=C[k]*L[d][k]
                
        if M<=X+S[d][j]:
            M=X+S[d][j]
            E=j

    T.append(E)
    for j in range(1,A+1):
        if j!=E:
            L[d][j]=L[d-1][j]+1
        else:
            L[d][j]=0

while time.time()-START<=1.95:
    e=randint(1,D)
    q=randint(1,A)

    V=g(e,q,S,C,T)
    if V>0 or random()>PROB:
        p=T[d]

        a=f(p,d+1,T)
        b=f(q,d+1,T)
        
        h=L[d-1][p]
        for i in range(d,a):
            h+=1
            L[i][p]=h

        m=0
        for j in range(d,b):
            L[j][q]=m
            m+=1
        T[d]=q
        
for i in range(1,D+1):
    print(T[i])


### FIXED CODE ###

from random import randint
A=26

D=int(input())

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

S=[0]*D
for i in range(D):
    S[i]=list(map(int,input().split()))

for j in range(D):
    print(randint(1,A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<=k が作れるか
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        for j in range(max(0,k-A[i]),k+1):
            if((dp>>j)&1):
                return True
        return False




    print(bisection(0,n-1,check,left=False))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()
### BUGGY CODE ###

import math
import sys
from itertools import accumulate
from functools import reduce
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    L = [list(map(int,list(sys.stdin.readline().split()))) for i in range(M)]
    sL = sorted(L, key=lambda x : x[0])

    d = {}
    for l in sL:
        if l[0] not in d:
            d[l[0]] = [l[1]]
        else:
            d[l[0]].append(l[1])

    for v in d.values():
        v.sort()

    for l in L:
        key = l[0]
        val = l[1]
        num = d[key].index(val) + 1
        print("{}{}".format(str(key).zfill(6),str(num).zfill(6)))


### FIXED CODE ###

import sys

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    P = [0] * (N + 1)
    C = [0] * M

    for m in range(M):
        p, y = map(int, input().split())
        C[m] = [m, p, y, 0]
    C.sort(key=lambda x :x[2])

    for c in C:
        P[c[1]] += 1
        c[3] = P[c[1]]
    C.sort(key=lambda x :x[0])

    for c in C:
        print("{}{}".format(str(c[1]).zfill(6), str(c[3]).zfill(6)))
### BUGGY CODE ###

N = int(input())
c = input().split()

  
for i in range(N):
  print(c.count(str(i+1)))
  

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
b = [0]*N

for i in range(N-1):
  b[a[i]-1]+=1
  #print(a[i]-1)

for i in range(N):
  print(b[i])
### BUGGY CODE ###

input = raw_input

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

pairs = []
for i in range(N):
    pairs.append(list(map(int, input().split())))

pairs = sorted(pairs, key=lambda elm: -elm[1])
#print(pairs)

finish_day = -1
out = 0

not_done = [True for _ in range(M)]

for A, B in pairs:
    for i in range(M-A, -1, -1):
        if not_done[i]:
            out += B
            #print(A, B)
            not_done[i] = False
            break

print(out)

### FIXED CODE ###

#input = raw_input
#import numpy as np

from heapq import heappush, heappop

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

values = [[] for i in range(M+1)]
for i in range(N):
    A, B = map(int, input().split())
    if M >= A:
        values[A].append(-B)

#print(values)
out = 0
elms = []
for i in range(1, M+1):
    #print("values[i]", values[i])
    for elm in values[i]:
        heappush(elms, elm)
        
    if len(elms) >= 1:
        max_val = - heappop(elms)
        #print("mval", max_val)
        out += max_val

print(out)
### BUGGY CODE ###

#11
n = int(input())
a = list(map(int, input().split()))
 
flag = [a.count(a[i])-1 for i in range(n+1) ]
p = flag.index(1) + list(reversed(flag)).index(1)
 
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
mod = 10**9 + 7
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
def combination(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
 
for i in range(n+1):
    if ( p>=i ):
        c = combination(n+1, i+1) - combination(p, i)
    else:
        c = combination(n+1, i+1)
    print( int(c) )

### FIXED CODE ###


MOD = 10**9+7
n = int(input())
la = list(map(int,input().split()))
L = [-1]*(n+1)
l = 0
for i in range(n+1):
  a = la[i]
  if L[a] == -1:
    L[a] = i
  else:
    l = i - L[a] - 1
    break
 
MAX = n
factorial = [1, 1]
inverse = [0, 1]
inverse_factorial = [1, 1]
for i in range(2,MAX+1):
  factorial.append( (factorial[-1]*i)%MOD )
  inverse.append( (-inverse[MOD%i]*(MOD//i))%MOD )
  inverse_factorial.append( (inverse_factorial[-1]*inverse[-1])%MOD )
 
def C_MOD(n, k):
  if k < 0 or k > n:
    return 0
  k = min(k,n-k)
  return factorial[n] * inverse_factorial[k] * inverse_factorial[n-k] % MOD
 
print(n)
#print((2*C_MOD(n-1,1)-C_MOD(n-1-l,1)+C_MOD(n-1,2)+1)%MOD)
for i in range(2,n+1):
  if n > l+1:
    print((2*C_MOD(n-1,i-1)-C_MOD(n-1-l,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
  else:
    print((2*C_MOD(n-1,i-1)+C_MOD(n-1,i)+C_MOD(n-1,i-2))%MOD)
print(1)
### BUGGY CODE ###

N,K,Q = map(int,input().split())

Answer_list = list()
point_list = [K] *N
for i in range(0,Q):
    Answer_list.append(int(input()))

for j in Answer_list:
    for k in range(0,N):
        if k != j-1:
            point_list[k] -= 1

for l in point_list:
    if l <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N,K,Q = map(int,input().split())

Answer_list = list()
point_list = [0] *N
for i in range(0,Q):
    Answer_list.append(int(input()))

for j in Answer_list:
    point_list[j-1] += 1

for l in point_list:
    if Q - l >= K:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A_set:
    dict[a] = A.count(a) 

# k番目の値を除いたlistで同じ数字を引く回数を出力
for k in range(N):
    dict_work = dict.copy()
    ans = 0
    dict_work[A[k]] -= 1
    for d in dict_work.values():
        if d > 1:
            ans += (d * (d - 1)) // 2
    print(ans)


### FIXED CODE ###

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

# 各数字の個数を格納
dict = {}
for a in A:
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

# k番目の値を消さない場合の場合分けの個数
ans = 0
for d in dict.values():
    if d > 1:
        ans += (d * (d - 1)) // 2

# k番目の値を除いた場合に減る場合の数を引いて答えを出力
for k in range(N):
    w = dict[A[k]]
    # 減る数
    decrease = 0
    if w == 1:
        pass
    elif w == 2:
        decrease = -1
    elif w > 2:
        decrease = ((w - 1) * (w - 2) // 2) - (w * (w - 1) // 2 )
    print(ans + decrease)
### BUGGY CODE ###

N,T = map(int,input().split())
import numpy as np
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
arg = np.argsort(A)
A = np.array(A)[arg]
B = np.array(B)[arg]
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = A[i-1],B[i-1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,B[i-1]+dp[i-1][T-1])
print(M)

### FIXED CODE ###

N,T = map(int,input().split())
C = []
for i in range(N):
    a,b = map(int,input().split())
    C.append([a,b])
C.sort()
dp = [[0 for i in range(T)]for j in range(N+1)]
for i in range(1,N+1):
    a,b = C[i-1][0],C[i-1][1]
    for t in range(1,T):
        p = dp[i-1][t]
        if t >= a:
            q = dp[i-1][t-a] + b
            dp[i][t] = max(p,q)
        else:
            dp[i][t] = p
M = 0
for i in range(1,N+1):
    M = max(M,C[i-1][1]+dp[i-1][T-1])
print(M)
### BUGGY CODE ###

N = int(input())
x = list(int(i) for i in input().split())
b = list([] for i in range(N))
for i in range(N):
    for j in range(N):
        if j != i:
            b[i].append(x[j])
    b[i].sort()
    print(b[i][int(N/2-1)])

### FIXED CODE ###

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

X = []
for i, a in enumerate(A):
    X.append([a, i])

X.sort()

# Biになり得るのはX[m-1] or X[m] (m=N//2)
m = N//2
itoj = {}
for j in range(N):
    x, i = X[j]
    itoj[i] = j
for i in range(N):
    j = itoj[i]
    if j < m:
        print(X[m][0])
    else:
        print(X[m-1][0])
### BUGGY CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    B, C = map(int, input().split())
    for i in range(B):
        tmp = heappop(A)
        if C <= tmp:
            heappush(A, tmp)
            break
        heappush(A, C)

print(sum(A))


### FIXED CODE ###

from heapq import heapify, heappop, heappush
from sys import stdin

N, M = map(int, input().split())
A = list(map(int, stdin.readline().split()))
heapify(A)
BC = [None] * M
for i in range(M):
    BC[i] = tuple(map(int, stdin.readline().split()))
BC = sorted(BC, key=lambda x: x[1], reverse=True)

enough = False
for bc in BC:
    if enough:
        break
    for i in range(bc[0]):
        if bc[1] <= A[0]:
            enough = True
            break
        heappop(A)
        heappush(A, bc[1])

print(sum(A))
### BUGGY CODE ###

from collections import deque
def bfs():
    d = [[float("inf")]* m for i in range(n)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "S":
                sx = i
                sy = j
            if maze[i][j] == "G":
                gx = i
                gy = j
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 0
for a1 in range(n):
    for a2 in range(m):
        if maze[a1][a2] == ".":
            maze[a1][a2]  = "S"
            for a3 in range(n):
                for a4 in range(m):
                     if maze[a3][a4] == ".":
                        maze[a3][a4]  = "G"
                        ans = max(bfs(),ans)
                        maze[a3][a4]  = "."
            maze[a1][a2]  = "."
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
c = [input() for _ in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[-1] * w for _ in range(h)]
    d[sy][sx] = 0
    res = 0
    while que:
        y, x = que.popleft()
        res = max(res, d[y][x])
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == -1 and c[ny][nx] != "#":
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return res

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] != "#":
            ans = max(ans, bfs( j_, i_))

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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[]
c=[]
for _ in range(q):
    x,y=map(int,input().split())
    b.append(x)
    c.append(y)

d=[0]*100001
for i in a:
    d[i]+=1

for m,p in zip(b,c):
    minus=d[m]
    d[m]=0
    d[p]+=minus
    ans=0
    for i in range(len(d)):
        ans+=i*d[i]
    print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[]
c=[]
for _ in range(q):
    x,y=map(int,input().split())
    b.append(x)
    c.append(y)

d=[0]*100001
for i in a:
    d[i]+=1

ans=sum(a)
for m,p in zip(b,c):
    minus=d[m]
    d[m]=0
    d[p]+=minus
    ans+=(p-m)*minus
    print(ans)
### BUGGY CODE ###

N=list(map(int,(input().split(" "))))
teast=[]
K = N[3]
total=[]
c=0
for i in range(3):
    teast.append(list(map(int,input().split(" "))))
A=sorted(teast[0],reverse=True)
B=sorted(teast[1],reverse=True)
C=sorted(teast[2],reverse=True)

for i in range(N[0]):

    for j in range(N[1]):

        for k in range(N[2]):
            if i*j*k<=K:
                total.append(A[i] + B[j] + C[k])
            else:
                break

total_s=sorted(total,reverse=True)

for i in range(K):
    print(int(total_s[i]))

### FIXED CODE ###

from heapq import *

Q=[]
teast=[]
X,Y,Z,K=list(map(int,input().split(" ")))

for i in range(3):
    teast.append(list(map(int,input().split(" "))))

A=sorted(teast[0],reverse=True)
B=sorted(teast[1],reverse=True)
C=sorted(teast[2],reverse=True)

arg_hash={}
heappush(Q,(-A[0]-B[0]-C[0],0,0,0))
arg_hash[(0,0,0)]=1

for k in range(K):
    ans=heappop(Q)
    a,b,c=ans[1:]
    print(-ans[0])
    argA=(a+1,b,c)
    if a <X-1 and( not argA in arg_hash):
        arg_hash[argA]=1
        heappush(Q,(-A[a+1]-B[b]-C[c],)+argA)
    argB=(a,b+1,c)
    if b <Y-1 and( not argB in arg_hash):
        arg_hash[argB]=1
        heappush(Q,(-A[a]-B[b+1]-C[c],)+argB)
    argC=(a,b,c+1)
    if c <Z-1 and( not argC in arg_hash):
        arg_hash[argC]=1
        heappush(Q,(-A[a]-B[b]-C[c+1],)+argC)
### BUGGY CODE ###

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

def check(N, a):
    flag = True
    if( (a[-1] ^ a[1]) != a[0]):
        return False
    if( (a[-2] ^ a[0]) != a[-1]):
        return False
    for i in range(1, N-1):
        if( (a[i-1] ^ a[i+1]) != a[i]):
            return False
    return True

for ap in itertools.permutations(a):
    if check(N, list(ap)):
        print("Yes")
        sys.exit()
print("No")

### FIXED CODE ###

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

def mae(N, a):
    sum = a[0]
    for i in range(1, N):
        sum ^= a[i]
    return sum

if mae(N, a) == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

#kが木の頂点、vがそこからきた頂点
bit = [0 for _ in range(n)]
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)

dfs(0)
print(*value)

### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
l =  [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)

value = [0 for _ in range(n)]
for _ in range(q):
    p,q = map(int,input().split())
    value[p-1] += q

bit = [0 for _ in range(n)]
"""
def dfs(k):
    bit[k] = 1
    for i in l[k]:
        if bit[i]==0:
            value[i] += value[k]
            dfs(i)
"""
d = deque([0])
while d:
    a = d.popleft()
    bit[a] = 1
    for i in l[a]:
        if bit[i]==0:
            d.append(i)
            value[i] += value[a]
        

print(*value)