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

import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while (abs(ok - ng) > 1) and cnt <= 20:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 1:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

N = int(input())

# print(N)

ans = N
i = 1
while i < N:
    # print(i)
    
    div, mod = divmod(N, i)
    
    if mod == 0:
        # print(i)
        # print(div)
        # print(mod)
        
        ans = min(ans, ((i - 1) + (div - 1)))
    
    i += 1
    
print(ans)

### FIXED CODE ###

N = int(input())

# print(N)

ans = N
i = 1
while i * i <= N:
    # print(i)
    
    div, mod = divmod(N, i)
    
    if mod == 0:
        # print(i)
        # print(div)
        # print(mod)
        
        ans = min(ans, ((i - 1) + (div - 1)))
    
    i += 1
    
print(ans)
### BUGGY CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
    A = i-X
    B = K+X-i
    ans += cmb(A+X-1,X-1,mod)*power(25,A,mod)*power(26,B,mod)
    ans %= mod
print(ans)


### FIXED CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

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

inf = float("inf") # 正の無限大

N,K=map(int, input().split())
H=[0]+list(map(int, input().split()))
#print(N,H)

dp=[inf]*(N+1)
dp[1]=0
dp[2]=abs(H[2]-H[1])

for i in range(3,N+1):
	for k in range(1,K+1):
		if (i-k)>0:
			a = dp[i-k]+abs(H[i]-H[i-k])
			if dp[i]>a: dp[i]=a

print( dp[N] )


### FIXED CODE ###

inf = float("inf") # 正の無限大

N,K=map(int, input().split())
H=[0]+list(map(int, input().split()))
#print(N,H)

dp=[inf]*(N+1)
dp[1]=0
dp[2]=abs(H[2]-H[1])

for i in range(3,N+1):
	for k in range(1,K+1):
		if (i-k)>0:
			a = dp[i-k]+abs(H[i]-H[i-k])
			if dp[i]>a: dp[i]=a

print( dp[N] )
### 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()))
AB = []
for i in A:
    for j in B:
        AB.append(i + j)
AB = sorted(AB, reverse=True)[:K]
ABC = []
for i in AB:
    for j in C:
        ABC.append(i + j)

ABC = sorted(ABC, reverse=True)[:K]
for a in ABC:
    print(a)

### 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()))
AB = []
for i in A:
    for j in B:
        AB.append(i + j)


AB = sorted(AB, reverse=True)[:K]
C = sorted(C, reverse=True)
ans = []
for i in C:
    for j in AB:
        ans.append(i + j)

ans = sorted(ans, reverse=True)[:K]
for i in ans:
    print(i)
### BUGGY CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        ans += bisect_left(l[j+1:],a+b)
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        k = bisect_left(l,a+b)
        ans += k-j-1
print(ans)
### BUGGY CODE ###

N,M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
ans = [0 for _ in range(N)]
for i in range(M):
    start = LR[i][0]
    end = LR[i][1]
    for j in range(start-1, end):
        ans[j] += 1
cnt = 0
for k in ans:
    if k == M:
        cnt += 1

print(cnt)

### FIXED CODE ###

N,M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
L1 = []
R1 = []
for i in range(M):
    L1.append(LR[i][0])
    R1.append(LR[i][1])
if min(R1)>=max(L1):
    print(min(R1)-max(L1)+1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += ((l[i]*l[j])%1000000007)
print(ans%1000000007)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
sum_n[0] = l[0]
sumall = sum(l)
for i in range(1,n):
    sum_n[i] = sum_n[i-1] + l[i]
for i in range(n):
    ans += ((l[i]*(sumall-sum_n[i]))%1000000007)
print(ans%1000000007)
### BUGGY CODE ###

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

X = 1
for i in range(N):
    X = X*AN[i]
if X <= 10**18:
    print(X)
else:
    print(-1)

### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
    exit()
    
for i in range(N):
    ans *= A[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
c = ["#"*(W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#"*(W+2)]


def bfs(start):
	queue = deque([start])
	visited = [[False for _ in range(W+2)] for _ in range(H+2)]
	tekazu = [[0 for _ in range(W+2)] for _ in range(H+2)]
	num = 0
	while queue:

		label = queue.pop()
		
		if label not in visited:
			visited.append(label)
			#print(visited)
			if c[label[0] + 1][label[1]] == "." and [label[0] + 1, label[1]] not in visited:
				queue.appendleft([label[0] + 1, label[1]])
				tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1
				num = max(num, tekazu[label[0] + 1][label[1]])

			if c[label[0] - 1][label[1]] == "." and [label[0] - 1, label[1]] not in visited:
				queue.appendleft([label[0] - 1, label[1]])
				tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1
				num = max(num, tekazu[label[0] - 1][label[1]])

			if c[label[0]][label[1] + 1] == "." and [label[0], label[1] + 1] not in visited:
				queue.appendleft([label[0], label[1] + 1])
				tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1
				num = max(num, tekazu[label[0]][label[1] + 1])

			if c[label[0]][label[1] - 1] == "." and [label[0], label[1] - 1] not in visited:
				queue.appendleft([label[0], label[1] - 1])
				tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
				num = max(num, tekazu[label[0]][label[1] - 1])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if c[h][w] == ".":
			ans = max(ans, bfs([h, w]))
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
c = ["#"*(W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#"*(W+2)]


def bfs(start):
	queue = deque([start])
	#visited = [[False for _ in range(W+2)] for _ in range(H+2)]
	tekazu = [[-1 for _ in range(W+2)] for _ in range(H+2)]
	tekazu[start[0]][start[1]] = 0
	num = 0
	while queue:

		label = queue.pop()
		
			#print(visited)
		if c[label[0] + 1][label[1]] == "." and tekazu[label[0] + 1][label[1]] < 0:
			queue.appendleft([label[0] + 1, label[1]])
			tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] + 1][label[1]])

		if c[label[0] - 1][label[1]] == "." and tekazu[label[0] - 1][label[1]] < 0:
			queue.appendleft([label[0] - 1, label[1]])
			tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] - 1][label[1]])

		if c[label[0]][label[1] + 1] == "." and tekazu[label[0]][label[1] + 1] < 0:
			queue.appendleft([label[0], label[1] + 1])
			tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] + 1])

		if c[label[0]][label[1] - 1] == "." and tekazu[label[0]][label[1] - 1] < 0:
			queue.appendleft([label[0], label[1] - 1])
			tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] - 1])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if c[h][w] == ".":
			ans = max(ans, bfs([h, w]))
print(ans)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if not visit[i]:
			visit[i] = True
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = []
	visit = [False] * N
	visit[0] = True
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

	# print(Wlist)
	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)


#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	#葉の場合の処理
	# for i in range(N):
	# 	if Nedge[i] == 1:
	# 		W[i] = 1

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

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

N = int(input())
D = []
for _ in range(N):
  D.append(int(input()))
 
for i in range(len(D)):
    TD = D.copy()
    del(TD[i])
    print(max(TD))

### FIXED CODE ###

from copy import copy

N = int(input())
D = []
for _ in range(N):
    D.append(int(input()))

DD = copy(D)
v1 = max(D)
m1 = D.index(v1)

del D[m1]
v2 = max(D)

[print(v2) if i == v1 else print(v1) for i in DD]
### BUGGY CODE ###

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

b.sort(reverse=True)

if len(b) <= a[1]:
    print("0")
else :
    for i in  range(a[1]):
        del b[0]
    print(sum(b))


### FIXED CODE ###

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

if len(b) <= a[1]:
    print("0")
elif a[1]==0:
    print(sum(b))
else:
    b.sort(reverse=True)
    print(sum(b[a[1]:]))
### BUGGY CODE ###

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

ans=-float('inf')

v_score={}

def get_loop_score(start): # return loop len and its loop score
    if start in v_score:
        return v_score[start]

    now_p=0
    visited=set()
    nxt=p[start]-1

    while True:
        nxt=p[nxt]-1
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]

    for v in visited:
        v_score[v]=now_p
    return now_p
def simulate(start,nokori): # ret max possible score
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]

    while True:
        nxt=p[nxt]-1
        visited.add(nxt)
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==nokori:
            break

    return max(p_lis)
for i in range(n):
    p_lis=[]

    cnt=0
    now_p=0
    nxt=p[i]-1

    visited=set()

    while True:
        now_p+=c[nxt]
        nxt=p[nxt]-1
        p_lis.append(now_p)

        cnt+=1
        if cnt==k:
            break

        if k>5010 and nxt in visited:
            break
        visited.add(nxt)

    if cnt!=k: # loop detected
        nokori = k-cnt
        loop_score=get_loop_score(nxt)
        if loop_score <= 0: # no loop
            nokori=len(visited)
        else: # loop as much as possible
            loops = nokori//len(visited) - 1
            now_p+= loops*loop_score
            nokori = loops*len(visited)

        score = simulate(nxt,nokori)
        p_lis.append(score)

    ans=max(ans,max(p_lis))

print(ans)

### FIXED CODE ###

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

def sim(start,mx): # simulate mx step from start, returns max_score
    if mx==0:
        return 0
    now_p=0
    nxt=p[start]-1
    cnt=0
    p_lis=[]

    while True:
        nxt=p[nxt]-1
        now_p+=c[nxt]
        p_lis.append(now_p)
        cnt+=1
        if cnt==mx:
            break

    return max(p_lis)

visited_p=set() # already checked flag
cycle_score=[] # cycle loop score
cycle_points=[]
now_cycle=0

for i in range(n):
    if i in visited_p:
        continue
    visited_p.add(i)
    now_p=0
    nxt=p[i]-1
    visited=set()
    while True:
        nxt=p[nxt]-1
        visited_p.add(nxt)
        if nxt in visited:
            break
        visited.add(nxt)
        now_p+=c[nxt]
    cycle_score.append(now_p)
    cycle_points.append(list(visited))

ans=-float('inf')

for c_num in range(len(cycle_score)):
#    print(c_num,cycle_score[c_num],cycle_points[c_num])
    cycle_len=len(cycle_points[c_num])
    for start in cycle_points[c_num]:

        if cycle_score[c_num]<0: # no loop, just check min(loop_len,k)
            score = sim(start,min(cycle_len,k))
            ans=max(ans,score)

        else: # loop as many as possible
            loop_num = max(0,(k // cycle_len) - 1)
            nokori=k-loop_num*cycle_len
            score = sim(start,nokori) + loop_num*cycle_score[c_num]
            ans=max(ans,score)

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

import copy

#メイン部
N,M=map(int,input().split())

V=list(range(1,N+1))
H={v:set() for v in V}
L={v:None for v in V}

for i in range(M):
    v,w=map(int,input().split())
    H[v].add(w)
    H[w].add(v)

X=set()
Y={V[0]}

while X!=Y:
    Z=Y-X
    X=copy.deepcopy(Y)
    
    for v in Z:
        K=[u for u in H[v] if u not in Y]
        for x in K:
            Y.add(x)
            L[x]=v

if set(V)==X:
    print("Yes")
    for i in range(2,N+1):
        print(L[i])
else:
    print("No")

### FIXED CODE ###

import copy
import collections

#メイン部
N,M=map(int,input().split())

V=list(range(1,N+1))
H={v:set() for v in V}
L={v:None for v in V}

for i in range(M):
    v,w=map(int,input().split())
    H[v].add(w)
    H[w].add(v)

Q=collections.deque()
Q.append(V[0])

L[1]=1
n=1

while Q:
    x=Q.popleft()
    for v in H[x]:
        if L[v]!=None:
            continue
        L[v]=x
        n+=1
        Q.append(v)

if n==N:
    print("Yes")
    for i in range(2,N+1):
        print(L[i])
else:
    print("No")
### BUGGY CODE ###

N,Y=map(int,input().split())
A=[]
for i in range(Y//10000+1):
    for j in range((Y-i*10000)//5000+1):
        c1=(Y-10000*i-5000*j)/1000
        c2=N-i-j
        if c1==c2:
            A=[i,j,c1]
            break
        if c1!=c2:
            continue
if len(A)==0:
    print("-1 -1 -1")
else:
    A[2]=int(A[2])
    #intは整数、floatは少数
    print(str(A[0])+" "+str(A[1])+" "+str(A[2]))

### FIXED CODE ###

N,Y=map(int,input().split())
A=[]
for i in range(Y//10000+1):
    for j in range((Y-i*10000)//5000+1):
        c1=(Y-10000*i-5000*j)/1000
        c2=N-i-j
        if c1==c2:
            A=[i,j,c1]
            break
        if c1!=c2:
            continue
if len(A)==0:
    print("-1 -1 -1")
else:
    A[2]=int(A[2])
    #intは整数、floatは少数
    print(str(A[0])+" "+str(A[1])+" "+str(A[2]))
### BUGGY CODE ###

s = input()
k = int(input())

dic = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        s0 = s[i:j]
        if s0 not in dic:
            dic.append(s0)

print(sorted(dic)[k-1])

### FIXED CODE ###

import bisect

s = input()
k = int(input())

alpha_list = [chr(i) for i in range(97, 97+26)] #["a","b",...."c"]
dic = []
for i in range(len(s)):
    dic = sorted(dic)
    if k < bisect.bisect_left(dic,s[i]):
        continue
    for j in range(i+1, min(i+6, len(s)+1)):
        s0 = s[i:j]
        
        if s0 not in dic:
            dic.append(s0)

print(sorted(dic)[k-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = list(map(int, input().split()))
H = sorted(list(map(int, input().split())), reverse=True)

if N <= K:
    print(0)
    sys.exit()

for _ in range(K):
    H.pop(0)

print(sum(H))


### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

N, K = list(map(int, input().split()))
H = np.sort(np.array(list(map(int, input().split()))))[::-1]

if N <= K:
    print(0)
    sys.exit()

print(np.sum(H[K:]))
### BUGGY CODE ###

from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()
    remain_user.discard(now)

    if watch[now] == 0:
        count += 1
        watch[now] = 1

    if now in friends_map:
        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)


### FIXED CODE ###

from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {n : set() for n in range(N)}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    friends_map[a].add(b)
    friends_map[b].add(a)
    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()

    if watch[now] == 0:
        remain_user.discard(now)
        watch[now] = 1
        count += 1

        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)
### BUGGY CODE ###

def comb(n, k):
    x, y = 1, 1
    if 2*k > n:
        k = n - k
    for i in range(k):
        x *= n - i
        y *= i + 1
    return x//y

N, M, K = map(int, input().split())
print((sum(i*(N-i)*M**2 for i in range(N))+sum(i*(M-i)*N**2 for i in range(M)))*comb(N*M-2, K-2) % (10**9+7))

### FIXED CODE ###

mod = 10**9 + 7

def comb(n, k):
    x, y = 1, 1
    k = min(k, n-k)
    for i in range(k):
        x *= n - i
        x %= mod
        y *= i + 1
        y %= mod
    return x*pow(y, mod-2, mod) % mod

N, M, K = map(int, input().split())
print((sum(i*(N-i)*M**2 for i in range(N))+sum(i*(M-i)*N**2 for i in range(M)))*comb(N*M-2, K-2) % mod)
### 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()))


C.sort()
C.reverse()
AB =[0]*(X*Y)

for i in range(X):
    for j in range(Y):
        AB[i*Y+j] =  A[i] + B[j]
        
AB.sort()
AB.reverse()
K2 = min(K,X*Y)
AB = AB[0:K2]
ABC = [0] * (K2*Z)
for i in range(K2):
    for j in range(Z):
        ABC[i*Z+j] = AB[i] + C[j]
        
ABC.sort()
ABC.reverse()
ABC = ABC[0:K]
for i in ABC:
    print(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()))


C.sort()
C.reverse()
AB =[0]*(X*Y)

for i in range(X):
    for j in range(Y):
        AB[i*Y+j] =  A[i] + B[j]
        
AB.sort()
AB.reverse()
K2 = min(K,X*Y)
AB = AB[0:K2]
ABC = [0] * (K2*Z)
for i in range(K2):
    for j in range(Z):
        ABC[i*Z+j] = AB[i] + C[j]
        
ABC.sort()
ABC.reverse()
ABC = ABC[0:K]
for i in ABC:
    print(i)