Harryxun/sft_time huggingface dataset:
### BUGGY 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 in range(h) for j in range(w) if S[i][j]=='#']
    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()

### 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 copy
n = int(input())
a = list(map(int,input().split()))


k = 1
s = 0
count = 0


for i in range(len(a)):
    if k in a:
        s = a.index(k)
        a = a[s:]
        k += 1
        count += 1
    else:
        break

if k == 1:
    print(-1)
else:
    print(n-(k-1))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
j=1
for i in range(N):
    if j==A[i]:
        j+=1
 
if j==1:
  print(-1)
else:
  print(N-j+1)
### BUGGY CODE ###

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

ans, ai = 0, 10**9
for i in range(N-K+1):
  sum = 0
  for k in range(K):
    sum += p[i+k]
  ans = max(ans, sum)
  if ans == sum:
    ai = i

ans, num = 0, 0
for i in range(ai, ai+K):
  tmp = 0
  for j in range(1,p[i]+1):
    tmp += j
  ans += tmp/p[i]

print(ans)

### FIXED CODE ###

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

ans, ai = 0, -1
sum = 0
for i in range(N-K+1):
  if i == 0:
    for k in range(K):
      sum += p[i+k]
  else:
    sum = sum - p[i-1] + p[i+k]
  ans = max(ans, sum)
  if ans == sum:
    ai = i

dp = [0]*1001
dp[0] = 0
for i in range(1000):
  dp[i+1] = i+1 + dp[i]

ans = 0.0
for i in range(ai, ai+K):
  ans += dp[p[i]]/p[i]

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

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

for i in range(n-1):
  while True:
    if(a[i]+a[i+1] > x):
      if(a[i+1]>0):
        a[i+1]=a[i+1]-1
        count=count+1
        continue
      else:
        a[i]=a[i]-1
        count=count+1
        continue
    else:
      break

print(count)

### FIXED CODE ###

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

for i in range(n-1):
  if(a[i]+a[i+1] > x):
    sa=(a[i]+a[i+1])-x
    count=count+sa

    if(a[i+1] > 0 and sa <= a[i+1]):
      a[i+1]=a[i+1]-sa
    else:
      a[i+1]=0

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

n,k=map(int,input().split())
d=0
for a in range(1,n+1):
 for b in range(k-a%k,n+1,k):
   for c in range(k-a%k,n+1,k):
    if (a+b)%k==0 and (b+c)%k==0 and (c+a)%k==0:d+=1
print(d)

### FIXED CODE ###

n,k=map(int,input().split())
if k%2==0:
 if n%k<k/2:print((n//k)**3+(n//k)**3)
 else:print((n//k)**3+((n//k)+1)**3)
else:print((n//k)**3)
### BUGGY CODE ###

# D
import math
A,B = map(int,input().split())

def cf(x1,x2):
    cf=[1]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def coprime(a, b):
    return len(cf(a, b)) == 1

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
ans = 0
for i in cf(A,B):
    if (is_prime(i)):
        ans += 1
print(ans+1)

### FIXED CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

c = set(make_divisors(a))
d = set(make_divisors(b))
e = list(c & d)

f = []
for i in range(len(e)):
        if is_prime(e[i]):
            f.append(e[i])
print(len(f) + 1)
### BUGGY CODE ###

import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]


xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()





### FIXED CODE ###

import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]
cnt2 = [[10**10 for _ in range(W)] for _ in range(H)]



xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10 and cnt[nx][ny]<cst+1:
                    break
                elif cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
for i in range(m):
    ab[i].sort()
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    if remove >= 1:
        while ab[remove - 1][0] < end[1]:
            remove -= 1
            if remove == 0:
                break
    del ab[(remove):]
    count += 1
print(int(count))

### FIXED CODE ###

n, m = map(int, input().split())
l = []
for i in range(m):
    a, b = map(int, input().split())
    l.append((b, a))
l.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline # 入出力高速化

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

def main():
    N, Q = map(int, input().split())
    tl = list() # イベントタイムライン
    points = list()
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
        points.append(X)
        
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    
    tl.sort()
    points.sort()
    M = len(points)
    comp = {e:i for i, e in enumerate(points)} # 座標圧縮
    B = BIT(M + 20)
 
    for t, c, x in tl:
        if c == 0: # erase
            B.bitadd(comp[x], -1)
        elif c == 1: # insert
            B.bitadd(comp[x], 1)
        else: # min
            idx = B.lower_bound(1)
            print(-1 if idx > M + 10 else points[idx])
    return
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def check(a,b):
    if b == 0 :
        return a
    return check(b,a%b)
def check2(x,y,p):
    for i in range(p+1,min(x,y)+1):
        if x % i == 0 and y % i == 0 :
            return i
A,B = map(int,input().split())
ans = 1
p = 1
while True :
    c = check(A,B)
    if c == 1 :
        break
    p = check2(A,B,p)
    while True :
        if A % p == 0 and B % p == 0 :
            A = (A//p)
            B = (B//p)
        else :
            break
    ans += 1
print(ans)

### FIXED CODE ###

def gcd(x, y):
    if y == 0 :
        return x
    else:
        return gcd(y,x%y)
def prime(x):
    global  ans
    m = x ** (0.5)
    for i in range(2,int(m+1)):
        if x % i == 0 :
            while True:
                if x % i != 0 :
                    break
                else:
                    x = (x//i)
            ans +=1
    if x != 1 :
        ans += 1
    return ans
A,B = map(int,input().split())
t = gcd(A,B)
ans = 1
print(prime(t))
### BUGGY CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
b = sorted(a,reverse=True)
if b[0] == b[1] and b[0] == max(a):
    for i in range(n):
        print(max(a))
else:
    for i in range(n):
        if a[i] == max(a):
            print(max(b[1:]))
        else:
            print(max(a))

### FIXED CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
A = max(a)
b = sorted(a,reverse=True)
import collections
c = collections.Counter(a)
if c[A] >= 2:
    for i in range(n):
        print(A)
else:
    for i in range(n):
        if a[i] == A:
            print(b[1])
        else:
            print(A)
### BUGGY CODE ###

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

# good = [False] * N

# for _ in range(M):
#     A, B = tuple(map(int, input().split()))
#     H_A, H_B = Hs[A-1], Hs[B-1]
#     if H_A < H_B:
#         good[B-1] = True
#         good[A-1] = False
#     elif H_B < H_A:
#         good[A-1] = True
#         good[B-1] = False
#     else:
#         good[A-1] = good[B-1] = False

# print(sum([v == True for v in good]))

path = [[0] * N for _ in range(N)]
for _ in range(M):
    A, B = tuple(map(int, input().split()))
    H_A, H_B = Hs[A-1], Hs[B-1]
    path[A-1][B-1] = H_B
    path[B-1][A-1] = H_A

print(sum(all(Hs[i] > h for h in p) for i, p in enumerate(path)))


### FIXED CODE ###

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

good = [True] * N

for _ in range(M):
    A, B = tuple(map(int, input().split()))
    H_A, H_B = Hs[A-1], Hs[B-1]
    if H_A < H_B:
        good[A-1] = False
    elif H_B < H_A:
        good[B-1] = False
    else:
        good[A-1] = good[B-1] = False

print(sum([v == True for v in good]))

# path = [[0] * N for _ in range(N)]
# for _ in range(M):
#     A, B = tuple(map(int, input().split()))
#     H_A, H_B = Hs[A-1], Hs[B-1]
#     path[A-1][B-1] = H_B
#     path[B-1][A-1] = H_A

# print(sum(all(Hs[i] > h for h in p) for i, p in enumerate(path)))
### BUGGY CODE ###

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

for _  in range(Q):
  l, r = map(int,input().split())
  x = S[l-1:r]
  if("AC" in x):
    print(x.count("AC"))
  else:
    print(0)


### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for _ in range(Q):
  l, r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
A = [0]*N
cnt = 0
for i in range(N):
    A[i] = int(input())

A.sort()
a = list(set(A))
for c in a:
    if A.count(c) % 2 == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
cnt = 1
ans = 0
A.sort()
for i in range(N-1):
    if A[i] == A[i+1]:
        cnt += 1
    else:
        if cnt%2 == 1:
            ans += 1
        cnt = 1
if cnt%2 == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    count = 0
    foot = [0]
    is_loop = False

    for i in range(1,k):
        foot.append(a[foot[-1]])
        if foot.count(foot[-1]) == 2:
            st_i = foot.index(foot[-1], 0, len(foot)-1)
            lo_size = len(foot)-1 - st_i

            k -= st_i
            k %= lo_size
            
            print(foot[st_i+k]+1)
            is_loop = True
            break
    
    if not is_loop:
        print(a[foot[-1]]+1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    foot = [0]
    is_loop = False
    ed = np.zeros([n], dtype=int)
    ed[0] = 1

    for i in range(1,k):
        go = a[foot[-1]]
        foot.append(go)
        if ed[go] == 1:
            st_i = foot.index(foot[-1])
            lo_size = len(foot)-1 - st_i

            k -= st_i
            k %= lo_size
            
            print(foot[st_i+k]+1)
            is_loop = True
            break
        ed[go] = 1
    
    if not is_loop:
        print(a[foot[-1]]+1)


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

def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()
### BUGGY CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			new=True
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while new:
	p=0
	black_new=[]
	new=False
	black.sort()
	for i in range(h):
		for j in range(w):
			if p>=len(black):
				break
			if [i,j]==black[p]:
				p+=1
				if i!=0 and field[i-1][j]==False:
					field[i-1][j]=True
					black_new.append([i-1,j])
					new=True
				if i!=h-1 and field[i+1][j]==False:
					field[i+1][j]=True
					black_new.append([i+1,j])
					new=True
				if j!=0 and field[i][j-1]==False:
					field[i][j-1]=True
					black_new.append([i,j-1])
					new=True
				if j!=w-1 and field[i][j+1]==False:
					field[i][j+1]=True
					black_new.append([i,j+1])
					new=True
	black=black_new
	ans+=1
print(ans-1)




### FIXED CODE ###

h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="#":
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*pow(10,keta))%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                dp[i+1][j][l] %= MOD
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
                    dp[i+1][j+a][l] %= MOD
ans = dp[N][S][2]
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for i in range(x):
    for j in range(y):
        an.append(lisa[i]+lisb[j])
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[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(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])