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

import itertools
n, k = map(int, input().split())
cnt = 0
for i in itertools.combinations_with_replacement(range(1, n + 1), 3):
    if (i[0] + i[1]) % k == 0 and (i[1] + i[2]) % k == 0 and (i[2] + i[0]) % k == 0:
        cnt += len(list(set((itertools.permutations(i)))))
print(cnt)

### FIXED CODE ###

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

s = n // k
ans = s ** 3
if k % 2 == 0:
    s_ = (n + (k // 2)) // k
    ans += s_ ** 3
print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())

ws = []

for i in range(N):
    w = input()
    ws.append(Counter(w))

res = 0
for i in range(N-1):
    for j in range(i+1,N):
        if ws[i] == ws[j]:
            res += 1

print(res)

### FIXED CODE ###

from collections import Counter
N = int(input())

res =0
cd = {}

for i in range(N):
    w = "".join(sorted(input()))
    if cd.get(w, 0):
        res += cd[w]
        cd[w] += 1
    else:
        cd[w] = 1
print(res)
### BUGGY CODE ###

import itertools as itr

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [['']*(lt+1) for _ in range(ls+1)]

for i, j in itr.product(range(1, ls+1), range(1, lt+1)):
    if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1]+s[i-1]
    else:
        dp[i][j] = max(dp[i][j],dp[i-1][j], dp[i][j-1], key=len)
    #print((i,j), dp[i][j])

print(dp[-1][-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = max(dp[si][ti]+1, dp[si+1][ti], dp[si][ti+1])
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti], dp[si][ti+1])

ans = ''
si = ns
ti = nt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si-1][ti]: 
        si -= 1
    elif dp[si][ti] == dp[si][ti-1]:
        ti -= 1
    else:
        ans = s[si-1] + ans
        si -= 1
        ti -= 1

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


H, W, D = map(int, input().split())

MAP  = [None] * (H*W+1)
COST = {}

for i in range(H):
    for j, str_l in enumerate(input().split()):
        MAP[int(str_l)] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    keys = COST.keys()
    while L != R:
        way = '%s,%s' % (L, L+D)
        if way in keys:
            pass
        else:
            COST[way] = abs(MAP[L][0] - MAP[L+D][0]) + abs(MAP[L][1] - MAP[L+D][1])
            COST.keys()
        cost += COST[way]
        L    += D
    print(cost)


### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

n=int(input())
s=input()


for i in range(n//2,0,-1):
   for j in range(0,n-2*i+1):
      for k in range(j+i,n-i+1):
        if s[j:j+i]==s[k:k+i]:
          print(i)
          exit(0)
print(0)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7

#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)

#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

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

import math
from functools import reduce

def gcd(*numbers):
  return reduce(math.gcd, numbers)

K = int(input())
total = 0

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += gcd(a,b,c)
print(total)

### FIXED CODE ###

import math
ans = 0
n = int(input())

for i in range(1,n+1):
    for j in range(1,n+1):
        l = math.gcd(i,j)
        for k in range(1,n+1):
            ans += math.gcd(k,l)
print(ans)
### BUGGY CODE ###

import numpy as np
import bisect
n = int(input())
l = np.array(list(map(int, input().split())))
l = np.sort(l)
ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += bisect.bisect_left(l[j+1:], l[i] + l[j])
print(ans)

### FIXED CODE ###

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


class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  # 10
  """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]

        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv


MOD = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
c = Combination(2000006)
ans = 0
for r in range(r1, r2 + 1):
    temp = c(c2 + r + 1, r + 1) - c(c1 + r + 1 - 1, r + 1)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)


### FIXED CODE ###

class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  # 10
  """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]

        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * \
                modinv[self.mod % i] % self.mod
        return modinv


MOD = 10**9 + 7

r1, c1, r2, c2 = map(int, input().split())
c = Combination(2000006)
ans = 0
for r in range(r1, r2 + 1):
    temp = c(c2 + r + 1, r + 1) - c(c1 + r + 1 - 1, r + 1)
    temp %= MOD
    ans += temp
    ans %= MOD
print(ans)
### BUGGY CODE ###

import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
#print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])

[print(np.min([np.abs(b[np.argmin(np.abs(b-t))]-t) + np.min(np.abs(a-b[np.argmin(np.abs(b-t))])), np.abs(a[np.argmin(np.abs(a-t))]-t) + np.min(np.abs(b-a[np.argmin(np.abs(a-t))]))])) for t in s[-hint[2]:]]

### FIXED CODE ###

import bisect
import numpy as np
 
hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

def search_min_pos(arr, target):
  index = bisect.bisect_left(arr, target)
  if 0 == index:
    dist = arr[index]
  else:
    dist = arr[index-1:index+1]
  if not isinstance(dist, list):
    dist = [dist]
  return dist

a_arr = s[:hint[0]]
b_arr = s[hint[0]:-hint[2]]
sum = 0
for t in s[-hint[2]:]:
  a_pos = search_min_pos(a_arr, t)
  b_pos = search_min_pos(b_arr, t)
  #print(t, a_pos, b_pos)
  min_dist = 10 ** 11
  for a in a_pos:
    b_against_a = search_min_pos(b_arr, a)
    for ba in b_against_a:
      min_dist = min([min_dist, abs(t-a)+abs(ba-a)])
  for b in b_pos:
    a_against_b = search_min_pos(a_arr, b)
    for ab in a_against_b:
      min_dist = min([min_dist, abs(t-b)+abs(ab-b)])
  print(min_dist)
### BUGGY CODE ###

import math

nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
if n - m == 1 or m - n == 1:
  ansn = math.factorial(n);
  ansm = math.factorial(m);
  print(ansn*ansm);
elif n == m :
  ansn = math.factorial(n);
  ansm = math.factorial(m);
  print(ansn*ansm*2);
else :
  print(0);

### FIXED CODE ###

nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
mod = 10**9+7
if n - m == 1 or m - n == 1:
	ansn = 1;
	for i in range(n) :
		ansn = (ansn % mod)*((n-i) % mod);
		ansm = 1;
	for j in range(m) :
	 	ansm = (ansm % mod)*((m-j) % mod);
	print((ansn*ansm) % mod);
elif n == m :
	ansn = 1;
	for i in range(n) :
		ansn = (ansn % mod)*((n-i) % mod);
		ansm = 1;
	for j in range(m) :
  		ansm = (ansm % mod)*((m-j) % mod);
	print((ansn*ansm*2) % mod);
else :
	print(0);
### BUGGY CODE ###

from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    move = product(range(-2, 3), repeat=2)
    near = [(dx, dy, (abs(dx) + abs(dy) >= 2)) for dx, dy in move]

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy, cnt in near:
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))


### FIXED CODE ###

from collections import deque
from itertools import product


def bfs(S):
    x, y = S
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([S])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for i, j in near_a:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] and s[j][i] == '.'):
                dist[j][i] = dist[y][x]
                que.appendleft((i, j))
        for i, j in near_b:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + 1 and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + 1
                que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs((Cw - 1, Ch - 1))[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)
### BUGGY CODE ###

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

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))


### FIXED CODE ###

n = int(input())
A = sorted(map(int, input().split()))
used = set()

U = A[-1]+1
is_prime = [1]*U
cnt = [0]*U
depri = 0
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and is_prime[a]:
        depri += 1
    if is_prime[a]:
        used.add(a)
        for q in range(2*a, U, a):
            is_prime[q] = 0
print(len(used)-depri)
### BUGGY CODE ###

n,w=map(int,input().split())
dp=[0]*(w+1)
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(dp[-1])

### FIXED CODE ###

n,w=map(int,input().split())
dp=[0]*(w+1)
for i in range(n):
    wi,vi=map(int,input().split())
    for j in range(w-wi,-1,-1):
        dp[j+wi]=max(dp[j+wi],dp[j]+vi)
print(dp[-1])
### BUGGY CODE ###

s=list(input())
t=list(input())

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

for i in range(lens):
    for j in range(lent):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=''
i,j=lens,lent

while i>=0 and j>=0:
    if dp[i-1][j]==dp[i][j]:i-=1
    elif dp[i][j-1]==dp[i][j]:j-=1
    else:
        ans=s[i-1]+ans
        i,j=i-1,j-1
print(ans)

### FIXED CODE ###

s=list(input())
t=list(input())

lens=len(s)
lent=len(t)

dp=[[0]*(lent+1) for _ in range(lens+1)]

for i in range(lens):
    for j in range(lent):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=''
i,j=lens,lent

while i>=0 and j>=0:
    if dp[i-1][j]==dp[i][j]:i-=1
    elif dp[i][j-1]==dp[i][j]:j-=1
    else:
        ans=s[i-1]+ans
        i,j=i-1,j-1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    num_m = 0
    num_a = 0
    num_r = 0
    num_c = 0
    num_h = 0
    inlis = []
    for i in range(n):
        s = input()
        if s in inlis:
            pass
        else:
            inlis.append(s)
            if s[0] == "M":
                num_m += 1        
            if s[0] == "A":
                num_a += 1
            if s[0] == "R":
                num_r += 1
            if s[0] == "C":
                num_c += 1
            if s[0] == "H":
                num_h += 1
    numlis = [num_m, num_a, num_r, num_c, num_h]
    ans = 0
    if sum(numlis) < 3:
        print(0)
    else:
        for i in range(5):
            for j in range(5):
                for k in range(5):
                    if i == j or i == k or j == k:
                        pass
                    else:
                        ans += numlis[i] * numlis[j] * numlis[k]
        print(int(ans/6))
                    


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    num_m = 0
    num_a = 0
    num_r = 0
    num_c = 0
    num_h = 0
    inlis = set()
    for i in range(n):
        s = input()
        if s in inlis:
            pass
        else:
            inlis.add(s)
            if s[0] == "M":
                num_m += 1        
            if s[0] == "A":
                num_a += 1
            if s[0] == "R":
                num_r += 1
            if s[0] == "C":
                num_c += 1
            if s[0] == "H":
                num_h += 1
    numlis = [num_m, num_a, num_r, num_c, num_h]
    ans = 0
    if sum(numlis) < 3:
        print(0)
    else:
        for i in range(5):
            for j in range(5):
                for k in range(5):
                    if i == j or i == k or j == k:
                        pass
                    else:
                        ans += numlis[i] * numlis[j] * numlis[k]
        print(int(ans/6))
                    


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

def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    s = input()

    def cut(cur, t):
        if cur >= len(s):
            return 0

        ret = -1 << 30
        if t != s[cur]:
            ret = max(ret, cut(cur + 1, s[cur]) + 1)
        if t != s[cur:cur + 2]:
            ret = max(ret, cut(cur + 2, s[cur:cur + 2]) + 1)
        return ret

    ans = cut(0, '')

    print(ans)


if __name__ == '__main__':
    main()

# 一文字か二文字


### FIXED CODE ###

s = input()
n = len(s)

a = []
cont = 0
c = ''
for ss in s:
    if c != ss:
        a.append(cont)
        c = ss
        cont = 1
    else:
        cont += 1
a.append(cont)

ans = 0
minus_flg = False
for aa in a[1:]:
    if minus_flg:
        aa -= 1
        minus_flg = False
    q, r = divmod(aa, 3)
    # print(aa, ans, q, r)
    if r == 0:
        ans += q * 2
    elif r == 1:
        ans += ((aa - 1) // 3) * 2 + 1
    else:
        ans += ((aa + 1) // 3) * 2
        minus_flg = True
if minus_flg:
    ans -= 1
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    for j in range(W):
        if not add(j):
            num += 1
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True

    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

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

from collections import Counter
# si と sj のアナグラムは Counter(si)==Counter(sj) で求められる
# 組の数を数える
N=int(input())
S=[Counter(input()) for n in range(N)]
c=0
l=[]
for s in S:
    if s in l:
        continue
    else:
        l.append(s)
        n=S.count(s)
        c+=(n*(n-1))//2
print(c)



### FIXED CODE ###

N=int(input())
S=["".join(sorted(input())) for n in range(N)]
d={}
for s in S:
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
c=0
for k in d:
    n=d[k]
    c+=(n*(n-1))//2
print(c)
### BUGGY CODE ###

import numpy as np

n = int(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

aaa = np.max(cnt)
ans2 = np.array(buf)[np.array(cnt) == aaa]
ans3 = np.sort(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### 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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
list1=[]
for i in range(X):
  for j in range(Y):
      list1.append(A[i]+B[j])
list1.sort(reverse=True)
list1=list1[:K+1]
list2=[]
for i in range(min(X*Y,K)):
  for j in range(Z):
    list2.append(list1[i]+C[j])
list2.sort(reverse=True)
for i in range(K):
  print(list2[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)
list1=[]
for i in range(X):
  for j in range(Y):
      list1.append(A[i]+B[j])
list1.sort(reverse=True)
list1=list1[:K+1]
list2=[]
for i in range(min(X*Y,K)):
  for j in range(Z):
    list2.append(list1[i]+C[j])
list2.sort(reverse=True)
for i in range(K):
  print(list2[i])
### BUGGY CODE ###

import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

memo = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

def calc(i1, i2, i3):
  if i1 == i2 == i3 == 0:
    return 0
  if memo[i1][i2][i3] > 0:
    return memo[i1][i2][i3]

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  memo[i1][i2][i3] = ex
  return ex

print(calc(n1, n2, n3))


### FIXED CODE ###

import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

dp = [[0]*(n2+n3+1) for _ in range(n3+1)]
dp[n3][n2] = 1.0
ans = 0

for i in range(s, 0, -1):
  dp2 = [[0]*(n2+n3+1) for _ in range(n3+1)]
  for i3 in range(n3, -1, -1):
    for i2 in range(min(n2+n3, (i-i3*3)//2), -1, -1):
      i1 = i-i3*3-i2*2
      i0 = n-i1-i2-i3
      if i2 < 0 or i1 < 0 or i0 < 0: continue
      e0 = n/(i1+i2+i3)
      dp2[i3][i2] += dp[i3][i2] * i1/(i1+i2+i3)
      ans += dp[i3][i2] * e0*(i1/(i1+i2+i3))
      if i2 > 0:
        dp2[i3][i2-1] += dp[i3][i2] * i2/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i2/(i1+i2+i3))
      if i3 > 0 and i2 < n2+n3:
        dp2[i3-1][i2+1] += dp[i3][i2] * i3/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i3/(i1+i2+i3))
  dp = dp2

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

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())

ans = list(S)
for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        ans.reverse()
        continue
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            ans = [c] + ans
        else:
            ans = ans + [c]
print(''.join(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().rstrip()
Q = int(input())
head = ''
tail = ''
rev = False

for _ in range(Q):
    query = list(input().split())
    if query[0] == '1':
        if rev:
            rev = False
        else:
            rev = True
    elif query[0] == '2':
        f = query[1]
        c = query[2].rstrip()
        if f == '1':
            if rev:
                tail = tail + c
            else:
                head = c + head
        else:
            if rev:
                head = c + head
            else:
                tail = tail + c
if rev:
    tmp = head + S + tail
    print(tmp[::-1])
else:
    print(head + S + tail)