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

import sys

input = sys.stdin.readline

def myindex(l, element, default=-1):
    if element in set(l):
        return l.index(element)
    else:
        return default

def main():
    H, W, D = map(int, input().split())
    grid = []; locale = [0]*(H*W)
    for i in range(H):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            x, y = i+1, j+1
            locale[t-1] = (x, y)
        grid.append(tmp)
    
    power = []
    for k in range(H*W-D):
        fr = locale[k]
        to = locale[k+D]
        need = abs(fr[0]- to[0]) + abs(fr[1] - to[1])
        power.append(need)

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        d = (R - L)//D
        print(sum(power[(L-1)::D][:d]))
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools

input = sys.stdin.readline

def myindex(l, element, default=-1):
    if element in set(l):
        return l.index(element)
    else:
        return default

def main():
    H, W, D = map(int, input().split())
    grid = []; locale = [0]*(H*W)
    for i in range(H):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            x, y = i+1, j+1
            locale[t-1] = (x, y)
        grid.append(tmp)
    
    power = []
    for k in range(H*W-D):
        fr = locale[k]
        to = locale[k+D]
        need = abs(fr[0]- to[0]) + abs(fr[1] - to[1])
        power.append(need)
    
    cum = []
    for d in range(D):
        cum.append([0] + list(itertools.accumulate(power[d::D])))

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        d = (L-1)%D
        dnum = (L-1)//D
        drange = (R-L)//D
        ans = cum[d][dnum+drange] - cum[d][dnum]
        print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

n_total = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      for k in range(j+1,N):
        if S[i] != S[k] and S[j] != S[k] and (j-i) != (k-j): 
          n_total+=1
print(n_total)

### FIXED CODE ###

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

n_R, n_G, n_B, n_total = 0, 0, 0, 0
for i in range(N):
  if S[i] == 'R':
    n_R+=1
  elif S[i] == 'G':
    n_G+=1
  else:
    n_B+=1
n_total += (n_R*n_G*n_B)
for j in range(1,N-1):
  i = j-1
  k = j+1
  while 1:
    if 0 <= i and k < N:
      if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
        #print(i,j,k, S[i], S[j], S[k])
        n_total-=1
    else:
      break
    i -= 1
    k += 1
print(n_total)
### BUGGY CODE ###

def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    import copy

    gcddict = {}
    adiv = []
    for i in range(n):
        primes = factorization(a[i])
        adiv.append(primes)
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = adiv[i]
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= pow(k, test[k], mod)
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))
resolve()

### FIXED CODE ###

def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])
    lsd = lsd % mod

    ans = 0
    for i in range(n):
        ans += (lsd * pow(a[i], mod-2, mod)) % mod

    print(int(ans % mod))

resolve()
### BUGGY CODE ###

N, M = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(M)]

ab_list.sort()

start_list = list(filter(lambda x: x[0] == 1, ab_list))

res = False


for start in start_list:
    if start[1] == N:
        res = True
        break
        
if not res:
    for start in start_list:
        if res:
            break
        for ab in list(filter(lambda x: x[0] == start[1], ab_list)):
            if ab[1] == N:
                res = True
                break

if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
co = []
ol = sorted(l)
nl = sorted(l,reverse=True)
for i in range(1,n):
    for j in range(1,n):
        if i<j:
            co.append(nl[i]+nl[j])
nco = list(reversed(co))
sk = 0
g = 0
for i in range(2,n):
    a = ol[i]
    x = nco[:(i)*(i-1)//2]
    ind = bisect.bisect(x,a)
    g += len(x)-ind
print(g)

### FIXED CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
g=0
for ai in range(n-2):
    for bi in range(ai+1,n-1):
        g+=max(0,bisect.bisect_left(l,l[bi]+l[ai])-1-bi)
print(g)
### BUGGY CODE ###

s=input()
if len(s)<5:
  print(0)
  exit()
ans=0
for i in range(len(s)-4):
  for j in range(i+4,len(s)+1):
    if int(s[i:j])%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

s=input()
res=0
t=1
p=[0]*2019
for i in map(int,s[::-1]):
  res+=i*t
  res%=2019
  p[res]+=1
  t*=10
  t%=2019
print(p[0]+sum((i*(i-1)//2) for i in p))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
total_act = 0
total_act2 = 1
total = 1
for i in range(n + 1):
    if str(i) not in a:
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
    else:
        total *= total_act
        total_act = 0
        total_act2 = 1
total *= total_act
print(total % 1000000007)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [input() for i in range(m)]
b = []
c = []
total_act = 0
total_act2 = 1
total = 1
if m == 0:
    for i in range(n + 1):
        if str(i) in a:
            total *= total_act
            total_act = 0
            total_act2 = 1
        else:
            total_act3 = total_act2 + total_act
            total_act2 = total_act
            total_act = total_act3
    total *= total_act
    print(total % 1000000007)
else:
    b.append(int(a[0]))
    for i in range(len(a) - 1):
        b.append(int(a[i + 1]) - int(a[i]) - 1)
        if int(a[i + 1]) - int(a[i]) - 1 == 0:
            print(0)
            exit()
    b.append(n - int(a[-1]))

    for i in range(max(b)):
        total_act3 = total_act2 + total_act
        total_act2 = total_act
        total_act = total_act3
        c.append(total_act)

    for i in b:
        total *= c[i - 1]
    print(total % 1000000007)
### BUGGY CODE ###

from bisect import *
n=int(input())
a=sorted(list(map(int, input().split())))
b=sorted(list(map(int, input().split())))
c=sorted(list(map(int, input().split())))
ans=0
for i in range(n):
  for j in range(bisect_right(b,a[i]),n):
    ans+=n-bisect_right(c,b[j])
print(ans)

### FIXED CODE ###

from bisect import *
n=int(input())
a=sorted(list(map(int, input().split())))
b=sorted(list(map(int, input().split())))
c=sorted(list(map(int, input().split())))
ans=0
for i in range(n):
    x=bisect_left(a,b[i])
    y=n-bisect_right(c,b[i])
    ans+=x*y
print(ans)
### BUGGY CODE ###

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

cor = pen = temp_pen = 0
temp_p = "0"
pen_dic={}
ac=[]

for _ in range(m):
  temp=input().split()
  if temp[0] in ac:
    continue
  if temp[1] == "AC":
    ac.append(temp[0])
    t = 0
    try:
      t = pen_dic[temp[0]]
    except:
      pass
    
    pen += t
  else:
    if not temp[0] in ac:
      t = 0
      try:
        t = pen_dic[temp[0]]
      except:
        pass
      pen_dic.update({temp[0]:t + 1})
print(len(set(ac)), pen)
 

### FIXED CODE ###

import sys
from collections import defaultdict

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

wa=defaultdict(lambda: 0)
already=set()
ac = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in already:
    continue

  if s == "AC":
    ac+=1
    already.add(p)
  else:
    wa[p] += 1

print(ac, sum(wa[i] for i in already))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
def gcd(x,y):
  while y != 0:
    k = x
    x = y
    y = k%y
  return  x
ans = 1
for i in range(N):
  flag = True
  if i == 0:
    p = A[1]
    for j in range(2,N):
      p = gcd(A[j],p)
      if ans >= p:
        flag = False
        break
    if flag:
      ans = p
  else:
    p = A[0]
    if p != 1:
      for j in range(1,N):
        if j != i:
          p = gcd(A[j],p)
        if ans >= p:
          flag = False
          break
      if flag:
        ans = p
    else:
      p = A[1]
      for j in range(2,N):
        if j != i:
          p = gcd(A[i],p)
        if ans >= p:
          flag = False
          break
      if flag:
        ans = p
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
def gcd(x,y):
  while y != 0:
    k = x
    x = y
    y = k%y
  return  x
L = [0]*(N+2)
R = [0]*(N+2)
for i in range(N):
  if L[i] == 0:
    L[i+1] = A[i]
  else:
    L[i+1] = gcd(max(L[i],A[i]),min(L[i],A[i]))
for i in range(N,-1,-1):
  if i == N:
    R[i+1] = 0
  elif i == N-1:
    R[i+1] = A[N-1] 
  else:
    R[i+1] = gcd(max(R[i+2],A[i]),min(R[i+2],A[i]))
ans = 1
for i in range(N):
  if L[i] == 0 or R[i+2] == 0:
    k = max(L[i],R[i+2])
    ans = max(ans,k)
  else:
    ans = max(ans,gcd(max(L[i],R[i+2]),min(L[i],R[i+2])))
print(ans)
### BUGGY CODE ###

from collections import defaultdict
d = defaultdict(int)
N = int(input())
for i in range(N):
    d[input()] += 1
ans = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
ans.sort()
for s in ans:
    print(s)

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
N = int(input())
for i in range(N):
    d[input()] += 1
m = max(d.values())
d = sorted(d.items(), key=lambda x:x[1])
d.reverse()
ans = []
for s in d:
    if s[1] == m:
        ans.append(s[0])
    else:
        break
ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in [-2, -1, 0, 1, 2]:
                for g in [-2, -1, 0, 1, 2]:
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        checkList.add((h, w))
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost

### FIXED CODE ###

from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        dist[h][w] = cost
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
input = stdin.readline

setrecursionlimit(10 ** 9)

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

abcd = [list(map(int, input().split())) for _ in range(Q)]

A = []


def make(tmp):
    if len(tmp) >= 2 * N:
        A.append(list(map(int, tmp.split())))
        return
    else:
        for j in range(int(tmp[len(tmp) - 2]), M + 1):
            make(tmp + str(j) + " ")


for i in range(1, M + 1):
    tmp = ""
    tmp += str(i)
    tmp += " "
    make(tmp)

ans = 0

for s in A:
    num = 0
    for q in range(Q):
        a, b, c, d = abcd[q]
        if s[b - 1] - s[a - 1] == c:
            num += d
    ans = max(ans, num)

print(ans)


### FIXED CODE ###

from sys import stdin
from itertools import combinations_with_replacement
input = stdin.readline

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

abcd = [list(map(int, input().split())) for _ in range(Q)]

s = list(range(1, M + 1))
ans = 0


for s in combinations_with_replacement(s, N):
    num = 0
    for q in range(Q):
        a, b, c, d = abcd[q]
        if s[b - 1] - s[a - 1] == c:
            num += d
    ans = max(ans, num)

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

import copy

n = int(input())

lis = []
for _ in range(n):
    lis.append(int(input()))
    
for i in range(n):
    tlis = copy.deepcopy(lis)
    tlis.remove(tlis[i])
    print(max(tlis))

### FIXED CODE ###

import copy

n = int(input())

lis = []
for _ in range(n):
    lis.append(int(input()))
    
slis = sorted(copy.deepcopy(lis), reverse=True)
    
m = max(lis)
s = sorted(slis, reverse=True)
s.remove(m)
sm = max(s)


for i in range(n):
    if lis[i] != m:
        print(m)
    else:
        print(sm)
### BUGGY CODE ###

import itertools

n = int(input())
l = list(map(int, input().split()))
total = 0
mod = 1000000007
L = itertools.combinations(l, 2)
for a,b in L:
    a = a % mod
    b = b % mod
    sum = (a * b) % mod
    total += sum
print(total % mod)

### FIXED CODE ###

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

a, b = map(int, input().split())
# a, b = 12, 18


def cf(a, b):
    return [i for i in range(2, (min(a, b)) + 1) if a % i == 0 and b % i == 0]


def furui(data):
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


data = cf(a, b)
ans = furui(data)
print(len(ans) + 1)


### FIXED CODE ###

from collections import defaultdict

A, B = map(int, input().split())


def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


d = gcd(A, B)
# print(d)


def f(v):
    dic = defaultdict(int)
    if v == 1:
        dic[1] = 1
        return dic
    for i in range(2, v):
        if i * i > v:
            break
        while v % i == 0:
            v //= i
            dic[i] += 1
    if v != 1:
        dic[v] += 1
    dic[1] = 1
    return dic


divisor = f(d)
# print(divisor)
print(len(divisor))
### BUGGY CODE ###

I = [int(_) for _ in open(0).read().split()]
N = I[0]
W, S, V = I[1::3], I[2::3], I[3::3]
dp = [-float('inf')] * (2 * 10**4 + 5)
dp[0] = 0
#dp[重さの総和]=その重さの総和になる最大価値
for s, w, v in sorted(zip(S, W, V), key=lambda swv: swv[0] + swv[1]):
    for wbefore in range(s, -1, -1):
        dp[wbefore + w] = max(dp[wbefore + w], dp[wbefore] + v)
print(max(dp))


### FIXED CODE ###

I = [int(_) for _ in open(0).read().split()]
N = I[0]
W, S, V = I[1::3], I[2::3], I[3::3]
dp = [-float('inf')] * (2 * 10**4 + 5)
dp[0] = 0
#dp[重さの総和]=その重さの総和になる最大価値
for s, w, v in sorted(zip(S, W, V), key=lambda swv: swv[0] + swv[1]):
    for wbefore in range(s, -1, -1):
        dp[wbefore + w] = max(dp[wbefore + w], dp[wbefore] + v)
print(max(dp))
### BUGGY CODE ###

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = dividemod(LR[k-1] * (L+R+1-k),k,mod)
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = dividemod(_LCR[k-1] * (L+C+R+1-k),k,mod)
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

### FIXED CODE ###

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

mod = int(1e9+7)
def powermod(p,n,mod):
    #if n==0: return 1
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)
### BUGGY 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()))
a_list.sort(reverse=True)
b_list.sort(reverse=True)
c_list.sort(reverse=True)

count = 0
candidates = {(0, 0, 0)}
used = set()
while True:
    max_x, max_y, max_z = (0, 0, 0)
    max_sum = -1
    for x, y, z in candidates:
        s = a_list[x] + b_list[y] + c_list[z]
        if s > max_sum:
            max_x, max_y, max_z = x, y, z
            max_sum = s
    if not (max_x, max_y, max_z) in used:
        print(max_sum)
        count += 1
        if count >= K:
            break
    candidates.remove((max_x, max_y, max_z))
    used.add((max_x, max_y, max_z))
    if max_x < X - 1:
        candidates.add((max_x + 1, max_y, max_z))
    if max_y < Y - 1:
        candidates.add((max_x, max_y + 1, max_z))
    if max_z < Z - 1:
        candidates.add((max_x, max_y, max_z + 1))


### FIXED CODE ###

import heapq

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)

candidates = []
heapq.heappush(candidates, (-(A[0] + B[0] + C[0]), 0, 0, 0))
used = {(0, 0, 0)}
for _ in range(K):
    s, i, j, k = heapq.heappop(candidates)
    print(-s)
    if i < X - 1 and (i+1, j, k) not in used:
        heapq.heappush(candidates, (-(A[i+1] + B[j] + C[k]), i+1, j, k))
        used.add((i+1, j, k))
    if j < Y - 1 and (i, j+1, k) not in used:
        heapq.heappush(candidates, (-(A[i] + B[j+1] + C[k]), i, j+1, k))
        used.add((i, j+1, k))
    if k < Z - 1 and (i, j, k+1) not in used:
        heapq.heappush(candidates, (-(A[i] + B[j] + C[k+1]), i, j, k+1))
        used.add((i, j, k+1))
### BUGGY CODE ###

N = int(input())
lis = []
indexes = []
cou = 1
ans = []
for _ in range(N):
  lis.append(input())
lis.sort()
if len(lis) != len(set(lis)):
  lis.append(999)
  for i in range(N):
    if lis[i] == lis[i+1]:
      cou += 1
    else:
      indexes.append(cou)
      cou = 1
  L = len(indexes)
  M = max(indexes)
  for k in range(L):
    if indexes[k] == M:
      ans.append(lis[sum(indexes[:k])])
  ans.sort()
  print(*ans)
else:
  print(*lis)

### FIXED CODE ###

N = int(input())
lis = []
indexes = []
cou = 1
ans = []
c_p = 0
for _ in range(N):
  lis.append(input())
lis.sort()
if len(lis) != len(set(lis)):
  lis.append("zzzzzzzzzzzzzz")
  for i in range(N):
    if lis[i] == lis[i+1]:
      cou += 1
    else:
      indexes.append(cou)
      cou = 1
  L = len(indexes)
  M = max(indexes)
  for k in range(L):
    if indexes[k] == M:
      ans.append(lis[c_p])
    c_p += indexes[k]
  print(*ans)
else:
  print(*lis)
### BUGGY CODE ###


import math


def primeFactorisation(x):
    res = set([1])
    while x % 2 == 0:
        res.add(2)
        x = x//2
    for i in range(3, int(math.sqrt(x)) + 1, 2):
        while (x % i == 0):
            res.add(i)
            x = x // i
    if (x > 2):
        res.add(x)
    return res


if __name__ == "__main__":
    a, b = map(int, input().split())
    divisors = set([x for x in range(1, max(a, b)) if (a % x == 0 and b % x == 0)])
    coPrimedivisors = set([1])
    for x in divisors:
        coPrimedivisors = coPrimedivisors.union(set(primeFactorisation(x)))
    print(len(coPrimedivisors))


### FIXED CODE ###


import math


def primeFactorisation(x):
    res = set([1])
    while x % 2 == 0:
        res.add(2)
        x = x//2
    for i in range(3, int(math.sqrt(x)) + 1, 2):
        while (x % i == 0):
            res.add(i)
            x = x // i

    if (x > 2):
        res.add(x)
    return res


if __name__ == "__main__":
    prevs = []
    a, b = map(int, input().split())
    fa = primeFactorisation(a)
    fb = primeFactorisation(b)
    fres = fa.intersection(fb)
    print(len(fres))