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

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
   
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

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

H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = max(H, W)

f = [1] * W
for i in range(1, H):
    f = [(f[j]+1) if (S[i-1][j:j+2] + S[i][j:j+2]).count('#') in [0,2,4] else 1 for j in range(W-1)] + [0]
    stk = []
    for j, v in enumerate(f):
        while len(stk) > 0 and f[stk[-1]] >= v:
            ans = max(ans, f[stk.pop()] * (j - (stk[-1] if len(stk) > 0 else -1)))
        stk.append(j)

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = max(H, W)

f = [1] * W
for i in range(1, H):
    f = [(f[j]+1) if (S[i-1][j:j+2] + S[i][j:j+2]).count('#') in [0,2,4] else 1 for j in range(W-1)] + [0]
    stk = []
    for j, v in enumerate(f):
        while len(stk) > 0 and f[stk[-1]] >= v:
            ans = max(ans, f[stk.pop()] * (j - (stk[-1] if len(stk) > 0 else -1)))
        stk.append(j)

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

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    A.sort()

    D = set()
    prev = -1
    for i in range(n):
        if A[i] == prev:
            D.add(A[i])
            A[i - 1] = -1
            A[i] = -1
        else:
            prev = A[i]

    A = [a for a in A if a != -1]
    ans = 0
    for i in range(len(A)):
        if len([d for d in D if A[i] % d == 0]) == 0:
            ans += 1
            D.add(A[i])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    ma = max(A)
    N = [0] * (10 ** 6 + 1)
    for a in A:
        for i in range(a, ma + 1, a):
            N[i] += 1

    ans = 0
    for a in A:
        if N[a] == 1:
            ans += 1

    print(ans)


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

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

key = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])
            
flag1 = 0
flag2 = 0
flag3 = 0
ans = 0



for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0
    
    for j in range(N):
        if key[i][0] == int(S[j]):
            flag1 = 1
            break
            
    if flag1 == 0:
        continue
            
    for k in range(j+1,N):
        if key[i][1] == int(S[k]):
            flag2 = 1
            break
            
    if flag2 == 0:
        continue
                
    for l in range(k+1,N):
        if key[i][2] == int(S[l]):
            flag3 = 1
            break
                            
    if flag1 == 1 and flag2 == 1 and flag3 == 1:
        ans += 1
        
print(ans)

### FIXED CODE ###

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

key = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            key.append([i,j,k])
            
flag1 = 0
flag2 = 0
flag3 = 0
ans = 0



for i in range(len(key)):
    flag1 = 0
    flag2 = 0
    flag3 = 0
    
    flag1 = S.find(str(key[i][0]))
    
    if flag1 == -1:
        continue
        
    flag2 = S.find(str(key[i][1]),flag1+1)
    
    if flag2 == -1:
        continue
        
    flag3 = S.find(str(key[i][2]),flag2+1)
    
    if flag3 == -1:
        continue
                            
    if flag1 != -1 and flag2 != -1 and flag3 != -1:
        ans += 1
        
print(ans)
### BUGGY CODE ###

s=int(input())
n=len(str(s))

ans=0
for L in range(4,n+1):
  for i in range(n-L+1):
    if ((s//(10**(n-L-i)))%(10**L))%2019==0:
      ans+=1

print(ans)

### FIXED CODE ###

import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
c,d=0,1
for i in s:
    c+=int(i)*d
    c%=2019
    d*=10
    d%=2019
    a[c]+=1
ans=0
for i in a:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

for i in range(1, M + 1):
    if M % i == 0 and i >= N:
        print(M // i)
        break


### FIXED CODE ###

# -*- coding: utf-8 -*-

import bisect

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

y = [1, M]
for i in range(2, int(M ** 0.5) + 1):
    if M % i == 0:
        y.append(i)
        y.append(M // i)

y.sort()
print(M // y[bisect.bisect_left(y, N)])
### BUGGY CODE ###

from math import sqrt
from itertools import product
from time import process_time as timer
 
import numpy as np

def helper(N,D):

  banned = set()
  for x in range(0, int(sqrt(D/2))+2):
    if D > x*x:
      y = sqrt(D-x*x)
      if y == int(y):
        y = int(y)
 
        for a,b in {(x,y),(y,x)}:
          for s,t in product((1,-1), repeat=2):
            banned.add((s*a,t*b))
  banned = list(banned)
  M = N*2
 
  grid = [[0 for _ in range(M)] for _ in range(M)]

  p0 = (0,0)
  stack = []
  while p0:

    stack.append(p0)
    grid[p0[0]][p0[1]] = 1

    while stack:
      x,y = stack.pop()
      t = grid[x][y]
      for dx,dy in banned:
        xx,yy = x+dx,y+dy
        if 0 <= xx < M and 0 <= yy < M and grid[xx][yy] == 0:
          grid[xx][yy] = -t
          stack.append((xx,yy))
    
    p0 = None
    for x in range(M):
      for y in range(M):
        if grid[x][y] == 0:
          p0 = (x,y)
          break
      if p0:
        break

  return np.array(grid)
 
N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N,D1)
g2 = helper(N,D2)
 
if np.count_nonzero(g1==1)*2 > M*M:
  g1 = g1==1
else:
  g1 = g1==-1
 
if np.sum(g1*g2) > 0:
  ans = g1&(g2==1)
else:
  ans = g1&(g2==-1)
 
 
for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
 
# print(ans.astype(int))
# print(np.sum(ans), N*N)

### FIXED CODE ###

from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  if D%2 == 1:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
    grid[:,1::2] = ~grid[:,1::2]
  elif D%4 == 2:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
  else:
    M = (N-1)//2+1
    D //= 4
    g = helper(M, D)
    grid = np.zeros((2*M,2*M),dtype=bool)
    grid[::2,::2] = g
    grid[1::2,::2] = g
    grid[::2,1::2] = g
    grid[1::2,1::2] = g
    grid = grid[:N,:N]
  return grid


N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N*2,D1)
g2 = helper(N*2,D2)
ans = g1&g2


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
### BUGGY CODE ###

n = int(input())
if n == 1:
    print(0)
else:
    import numpy as np
    lst = np.array([(elem + 1) for elem in range(n)])
    print(np.sum(lst[:-1]))

### FIXED CODE ###

n = int(input())
if n == 1:
    print(0)
else:
    print(n * (n - 1) // 2)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = [onem() for i in range(n)]

d = [a[0]]
co = 1
for i in range(1,n):
	for j in range(len(d)):
		if d[-(j+1)] < a[i]:
			d.pop(len(d)-1-j)
			d.insert(len(d)-j,a[i])
			break
	else:
		co += 1
		d.append(a[i])
print(co)












### FIXED CODE ###

import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

def LIS(L):
  L = L[::-1]
  LIS=[]
  for i in L:
    pos = bs.bisect_right(LIS,i) 
    if len(LIS) <= pos:
      LIS.append(i)
    else:
      LIS[pos]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())


print(LIS(a))
### BUGGY CODE ###

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=0
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        for k in range(count_C+1):
            for l in range(count_D+1):
                total=i*A+j*B+k*C+l*D
                if total!=0:
                    density=(k*C+l*D)/total
                    if total<=F and density<=E/(100+E) and max<=density:
                        max=density
                        ans[0]=total
                        ans[1]=k*C+l*D
print(' '.join(map(str, ans)))

### FIXED CODE ###

#ABC074C
A, B, C, D, E, F=map(int, input().split())
A=100*A
B=100*B
count_A=F//A
count_B=F//B
count_C=F//C
count_D=F//D
max=-1
ans=[0]*2
total=0
density=0
for i in range(count_A+1):
    for j in range(count_B+1):
        if i*A+j*B<=F and 0<i*A+j*B:
            for k in range(count_C+1):
                if i*A+j*B+k*C<=F:
                    for l in range(count_D+1):
                        total=i*A+j*B+k*C+l*D
                        if total!=0:
                            density=(k*C+l*D)/total
                            if total<=F and density<=E/(100+E) and max<density:
                                max=density
                                ans[0]=total
                                ans[1]=k*C+l*D
                                if density==E/(100+E):
                                    print(' '.join(map(str, ans)))
                                    exit()
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

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

allhiyatoi.sort(key=lambda x: x[1], reverse = True)

reward = [0] * (M+1)
finish = set([])
remain = set(range(M+1))
for hiya in allhiyatoi:
    if hiya[0]>M:
        continue
    now = remain - finish
    if max(now)<hiya[0]:
        continue
    for i in remain:
        if i<hiya[0]:
            continue
        if reward[i] == 0:
            reward[i] = hiya[1]
            finish.add(i)
            break

print(sum(reward))

### FIXED CODE ###

from heapq import heappush, heappop
 
N,M = map(int,input().split())

allhiyatoi = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    allhiyatoi[temp[0]].append(temp[1])
 
reward = 0
Q = []
for i in allhiyatoi:
    for j in i:
        heappush(Q,j*-1)
    if len(Q) == 0:
        continue
    reward -= (heappop(Q))

print(reward)
### BUGGY CODE ###

n = int(input())
power = 1
mod = 10**9 + 7
for i in range(1,n+1):
    power *= i
ans = power % mod
print(ans)


### FIXED CODE ###

import math
n=int(input())
mod = 10**9 + 7
ans = math.factorial(n)
print(ans % mod)
### BUGGY CODE ###

n = int(input())
lis = [0] + list(map(int, input().split())) + [0]
def abs(m):
  if m>0:
    return m
  return(-m)
tmp = []
for j in range(len(lis)-1):
    tmp.append(lis[j+1] - lis[j])
for i in range(len(tmp)-1):
    a = tmp[:i] + [tmp[i]+tmp[i+1]] + tmp[i+2:]
    print(sum(map(abs,a)))


### FIXED CODE ###

n = int(input())
lis = [0] + list(map(int, input().split())) + [0]
tmp = []
for j in range(len(lis)-1):
    tmp.append(lis[j+1] - lis[j])
lis = list(map(abs,tmp))
preans = sum(lis)
for i in range(len(tmp)-1):
    print(preans - lis[i] - lis[i+1] + abs(tmp[i] + tmp[i+1]))
### BUGGY CODE ###

import sys
import numpy as np

# input = sys.stdin.readline

s = list(input())

n = int(input())

for ii in range(n):
    q = input()
#     print("".join(s))
    if q[0] == "1":
        s = s[::-1]
    else:
        t, f, c = q.split()
        if f == "1":
            s.insert(0, c)
        else:
            s.append(c)
print("".join(s))

### FIXED CODE ###

# TLE
import sys
import numpy as np
from collections import deque

# input = sys.stdin.readline

s = list(input())

n = int(input())

d = deque(s)

reverse = False
for ii in range(n):
    q = input()
#     print("".join(s))
    if q[0] == "1":
        reverse += 1
        reverse %= 2
#         s = s[::-1]
    else:
        t, f, c = q.split()
        if f == "1":
            if reverse:
                d.append(c)
            else:
                d.appendleft(c)
        else:
            if reverse:
                d.appendleft(c)
            else:
                d.append(c)
                
if reverse:
    d.reverse()
print("".join(d))
### BUGGY CODE ###

from collections import deque
import numpy
H,W = list(map(int,input().split()))
A = [input().split() for i in range(H)]
place_h = [0,-1,0,1]
place_w = [1,0,-1,0]
black = 0
q = []
dist = [[-1 for i in range(W)] for j in range(H)]
for i in range(H):
    A[i] = list(A[i][0])
    for j in range(W):
        if A[i][j] == "#":
            black += 1
            q.append(deque([[i,j]]))
            dist[i][j] = 0

while len(q)>0:
    i = 0
    while i < black:
        if len(q[i]) == 0:
            q.pop(i)
            black -= 1
            continue
        vh,vw = q[i].popleft()
        for m in range(4):
            nvh = vh+place_h[m]
            nvw = vw+place_w[m]
            if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1:
                q[i].append([nvh,nvw])
                dist[nvh][nvw] = dist[vh][vw]+1
        i+=1
print(numpy.amax(dist))





### FIXED CODE ###

from collections import deque
import sys
def main():
    H,W = list(map(int,sys.stdin.readline().split()))
    place_h = [0,-1,0,1]
    place_w = [1,0,-1,0]
    black = 0
    q = deque([])
    dist = []
    A = []
    for i in range(H):
        a = sys.stdin.readline().split()
        a = list(a[0])
        dist_sub = []
        for j in range(W):
            if a[j] == "#":
                black += 1
                q.append([i,j])
                dist_sub.append(0)
            else:
                dist_sub.append(-1)
        A.append(a)
        dist.append(dist_sub)

    ans = 0
    
    while len(q) > 0:
        vh,vw = q.popleft()
        for m in range(4):
            nvh = vh+place_h[m]
            nvw = vw+place_w[m]
            if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1:
                q.append([nvh,nvw])
                dist[nvh][nvw] = dist[vh][vw]+1
                if ans < dist[nvh][nvw]:
                    ans = dist[nvh][nvw]

    print(ans)

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

N = int(input())
n = [0 for _ in range(N)]

def cob(m):
    if m <= 0:
        return m
    return m + cob(m-1)

# x > y > z
test = 0
for x in range(1,N+1):
    for y in range(1,x+1):
        for z in range(1,y+1):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if len(set([x,y,z])) == 3:
                cnt = 6
            elif len(set([x,y,z])) == 2:
                cnt = 3
            else:
                cnt = 1
            if ans > N:
                break
            n[ans-1] += cnt

for i in range(N):
    print(n[i])



### FIXED CODE ###

N = int(input())
n = [0 for _ in range(N)]

def cob(m):
    if m <= 0:
        return m
    return m + cob(m-1)

# x > y > z
test = 0
for x in range(1,N+1):
    for y in range(1,x+1):
        if N < x*y:
            break
        for z in range(1,y+1):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if len(set([x,y,z])) == 3:
                cnt = 6
            elif len(set([x,y,z])) == 2:
                cnt = 3
            else:
                cnt = 1
            if ans > N:
                break
            n[ans-1] += cnt

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

a,b,x=map(int,input().split())
ans=0
for s in range(a,b+1):
  if s%x==0:
    ans+=1
    break
ans+=(b-s)//x
print(ans)

### FIXED CODE ###

a,b,x=map(int,input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###


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

for i in range(n):
    a[i]=a[i]%m

count=0
cnt=0

for i in range(n):
    for j in range(i,n):
        cnt=(cnt+a[j])%m
        if cnt==0:
            count+=1
            
    cnt=0
    

print(count)






### FIXED CODE ###

import itertools
import collections

n, m = map(int, input().split())
a=list(map(int,input().split()))
b =[0]+ list(itertools.accumulate(a))
count=0
for i in range(n+1):
    b[i]=b[i]%m

b=collections.Counter(b)
b=b.most_common()

for i in range(len(b)):
    if b[i][1]>=2:
        count+=b[i][1]*(b[i][1]-1)//2
    else:
        break
print(count)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
B = []
for s in range(len(S)):
    B.append(S[s])
A = []
for q in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    C = []
    C = S[l-1:r]
    for c in range(len(C)-1):
        if C[c] + C[c+1]  == 'AC':
            cnt += 1
    A.append(cnt)
for a in A:
    print(a)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
s = [0]*N
A = []
for n in range(N-1):
    if S[n] + S[n+1] == 'AC':
        s[n+1] = s[n] + 1
    else:
        s[n+1] = s[n]
for q in range(Q):
    l, r = map(int, input().split())
    A.append(s[r-1] - s[l-1])
for a in A:
    print(a)
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(readline().split(),np.int64)
F = np.array(readline().split(),np.int64)

A.sort()
F.sort()
F=F[::-1]
 
new_list_a = np.array(A)
new_list_f = np.array(F)
 
for _ in range(K):
  time = new_list_f * new_list_a
  number_a = np.argmax(time)
  new_list_a[number_a] = new_list_a[number_a] - 1
  time = new_list_f * new_list_a
  
print(max(time))

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
### BUGGY CODE ###

H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[[] for i in range(330000)]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW[h].append(w)

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)

import sys
for i in range(len(LY)):
    for j in range(len(LX)):
        if LX[j] not in HW[LY[i]]: 
            print(MY+MX)
            sys.exit()
            
print(MY+MX-1)

### FIXED CODE ###

H,W,M=map(int,input().split())
Y=[0 for i in range(H+1)]
X=[0 for i in range(W+1)]
HW=[]
for i in range(M):
    h,w=map(int,input().split())
    Y[h]+=1
    X[w]+=1
    HW.append([h,w])

LY=[]
LX=[]
MY=max(Y)
MX=max(X)
for i in range(H+1):
    if Y[i]==MY:
        LY.append(i)
for i in range(W+1):
    if X[i]==MX:
        LX.append(i)

count=0
for i in range(M):
    if Y[HW[i][0]]==MY and X[HW[i][1]]==MX:
        count+=1

if count==len(LY)*len(LX):
    print(MY+MX-1)
else:
    print(MY+MX)
### BUGGY CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    global ans
    n,m = i_map()
    s = [0]*n
    g = [[0]*n for i in range(n)]
    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        g[a][b] = g[b][a] = 1

    def dfs(i):
        global ans
        s[i] = 1
        ans += 1
        for v in range(n):
            if g[i][v] == 0:
                continue
            if s[v] == 0:
                dfs(v)

    cnts = []

    for i in range(n):
        if s[i] == 0:
            trial = dfs(i)
            cnts.append(ans)
            ans = 0
    print(max(cnts))




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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


N, M = map(int, input().split())
to = [[] for _ in range(N)]
count = 0

for _ in range(M):
    A, B = map(lambda x:int(x) - 1, input().split())
    to[A].append(B)
    to[B].append(A)


def dfs(v, to, seen):
    global count
    seen[v] = True
    count += 1
    for nv in to[v]:
        if seen[nv]:
            continue
        dfs(nv, to, seen)


def main():
    global count
    seen = [False] * N
    cnts = []
    for i in range(N):
        if not seen[i]:
            dfs(i, to, seen)
            cnts.append(count)
            count = 0
    
    print(max(cnts))


if __name__ == "__main__":
    main()
### 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())

A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

import itertools
val_list = []

for a, b, c in itertools.product(A_list, B_list, C_list):
    val_list.append(a + b + c)
    
val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])
    


            


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

val_list = []


A_list = sorted(A_list, reverse=True)
B_list = sorted(B_list, reverse=True)
C_list = sorted(C_list, reverse=True)

#print(A_list)
#print(B_list)
#print(C_list)

for a in range(len(A_list)):
    if a + 1 > K:
        break
    for b in range(len(B_list)):
        if b + 1 > K:
            break
        if (a+1) * (b+1) > K:
            break
            
        for c in range(len(C_list)):
            if c + 1 > K:
                break
            if (a+1) * (b+1) * (c+1) > K:
                break
        
            val_list.append(A_list[a] + B_list[b] + C_list[c])

val_list = sorted(val_list, reverse=True)
for i in range(K):
    print(val_list[i])