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

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if i<j:
                for k in range(n):
                    if s[k]!=s[j] and s[i]!=s[k]:
                        if j<k:
                            if j-i==k-j:
                                ans-=1
                    
print(ans)
        

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b

for i in range(n):
    for j in range(n):
        if s[i]!=s[j]:
            if j-i<=n//2:
                if i<j:
                    d=j-i
                    k=j+d
                    if k<n:
                        if s[k]!=s[j] and s[i]!=s[k]:
                            ans-=1
                        

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

N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
startship=[]
secondship=[]
for i in range(M):
  if S[i][0]=='1':
    startship.append(S[i])
for v in startship:
  for n in range(M):
    if v[2] == S[n][0] and S[n][2] == str(N):
      print('POSSIBLE')
      exit()    
  
print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
from_1 = [False]*N
to_N = [False]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b-1] = True
    elif b == N:
        to_N[a-1] = True
for i in range(1, N):
    if from_1[i] and to_N[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import numpy as np
N = int(input())
S = np.array([list(input()) for i in range(N)])

ans = 0
flg = False
for a in range(N):
    S2 = np.roll(S, a, axis=0)
    for i in range(N):
        for j in range(N):
            if S2[i][j] != S2[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)

### FIXED CODE ###

N = int(input())
S = [list(input()) for i in range(N)]

ans = 0
flg = False
for a in range(N):
    S2 = S[a:] + S[:a]
    for i in range(N):
        for j in range(N):
            if S2[i][j] != S2[j][i]:
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        ans += 1

print(ans * N)
### BUGGY CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
passed = set()
queued = set()
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()
        if (h,w) in passed:
            continue
        passed.add((h,w))
        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))
                queued.add((nh,nw))
                nque.discard((nh,nw))

        for dh,dw in product(range(-2, 3), repeat=2):
            if [dh,dw] in [[0,0], [0,1], [0,-1], [1,0], [-1,0]]:
                continue
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

### FIXED CODE ###

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([(*c, 0)])
passed = set()
while que:
    h,w,dist = que.popleft()
#         print(f'{h=},{w=}')
    if (h,w) == d:
        print(dist)
        exit()
    if (h,w) in passed:
        continue
    passed.add((h,w))
    for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
            que.appendleft((nh, nw, dist))

    for dh,dw in [
        [-2,-2], [-2,-1], [-2,0], [-2, 1], [-2, 2], 
        [-1,-2], [-1,-1], [-1, 1], [-1, 2], 
        [0,-2], [0, 2], 
        [1,-2], [1,-1], [1, 1], [1, 2], 
        [2,-2], [2,-1], [2,0], [2, 1], [2, 2], 
    ]: 
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
            que.append((nh, nw, dist + 1))
print(-1)
### BUGGY 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):
    a=l[i]
    b=l[j]
    le=bisect.bisect_left(l,max(a-b,b-a)+1)
    ri=bisect.bisect_right(l,a+b-1)
    #print(le,ri)
    f=0
    if le<=i<=ri:
      f-=1
    if le<=j<=ri:
      f-=1
    if ri-le+f>0:
      ans+=ri-le+f
    #print(a,b,ans)

print(ans//3)

### 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):
    a=l[i]
    b=l[j]
    le=bisect.bisect_left(l,max(a-b,b-a)+1)
    ri=bisect.bisect_right(l,a+b-1)
    #print(le,ri)
    f=0
    if le<=i<=ri:
      f-=1
    if le<=j<=ri:
      f-=1
    if ri-le+f>0:
      ans+=ri-le+f
    #print(a,b,ans)

print(ans//3)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
  if A[i] == 0:
    continue
  else:
    if i == N - 1 or (i < N - 1 and A[i] != A[i+1]):
      ans += 1
    for j in range(i+1, N):
      if A[j] % A[i] == 0:
        A[j] = 0
print(ans)


### FIXED CODE ###

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )
### BUGGY CODE ###

import queue
n, m = map(int, input().split())
bridges = [map(int, input().split()) for _ in range(m)]

nodes = [[] for _ in range(n)] # いける島のリスト
ans = n*(n-1)//2
ans_list = []
q = queue.Queue()
for i in range(m):
    ans_list.append(ans)
    # 順番に橋をかけていく
    a, b = bridges[-(i+1)]
    if not a in nodes[b-1]:
        nodes[b-1].append(a)
        nodes[a-1].append(b)
        ans -= 1
    q.put((a,b))
    q.put((b,a))
    while not q.empty():
        # print(nodes)
        a,b = map(int, q.get())
        for j in nodes[a-1]:
            if not j in nodes[b-1] and j != b:
                nodes[b-1].append(j)
                nodes[j-1].append(b)
                ans -= 1
                q.put((j,b))
        for j in nodes[b-1]:
            if not j in nodes[a-1] and j != a:
                nodes[a-1].append(j)
                nodes[j-1].append(a)
                ans -= 1
                q.put((j,a))
# print(nodes)
for i in range(m):
    print(ans_list[-i-1])


### FIXED CODE ###

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n, m = map(int, input().split())
bridges = [map(int, input().split()) for _ in range(m)]
nodes = [[] for _ in range(n)] # いける島のリスト
ans = n*(n-1)//2
ans_list = []
u = UnionFind(n)
for i in range(m):
    ans_list.append(ans)
    # 順番に橋をかけていく
    a, b = bridges[-(i+1)]
    if u.isSameGroup(a, b):
        continue
    else:
        ans -= u.Count(a)*u.Count(b)
        u.Unite(a, b)

# print(nodes)
for i in range(m):
    print(ans_list[-i-1])
### BUGGY CODE ###

S = input()
MOD = 10 ** 9 + 7
dp = 1
p = 0

n = 1
for c in reversed(S):
  if c == '1':
    dp = (2 * dp + n) % MOD
  n *= 3 % MOD
print(dp)

### FIXED CODE ###

S = input()
MOD = 10 ** 9 + 7
dp = 1

n = 1
for c in reversed(S):
  if c == '1':
    dp = 2 * dp + n
  n *= 3
print(dp % MOD)
### BUGGY CODE ###

import sys

n, m = map(int, input().split())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
for x in sys.stdin.readlines():
    b, c = map(int, x.split())
    if c < a[0]:
        pass
    else:
        for i in range(b):
            if a[i] < c:
                a[i] = c
            else:
                break
        a.sort()
print(sum(a))

### FIXED CODE ###

import sys

n, m = map(int, input().split())
a = list(map(int, sys.stdin.readline().split()))
bc = [ tuple(map(int, x.split())) for x in sys.stdin.readlines()]
bc.sort(key = lambda x:x[1], reverse=True)
bc.append((n,0))
diff = []
for b, c in bc:
    diff += [c] * b
    if len(diff) > n:
        break

a += diff
a.sort()
print(sum(a[-n:]))
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(input())
t=[0]*n
for i in range(n-1):
    if s[i]+s[i+1]=="AC":
        t[i]=1
for i in range(q):
    l,r=map(int,input().split())
    print(sum(t[l-1:r-1]))

### FIXED CODE ###

import numpy as np
n,q=map(int,input().split())
s=list(input())
t=np.zeros(n+1,dtype=int)
for i in range(n-1):
    if s[i]+s[i+1]=="AC":
        t[i+1]=1
t=t.cumsum()
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    geta = 64
    inf = 1<<geta
    dist = [inf] * N
    dist[s] = 0
    Q = [s]
    dp = [0]*N
    dp[s] = 1
    while Q:
        k = hpp(Q)
        dn = k>>geta
        vn = k^(dn<<geta)
        if dn > dist[vn]:
            continue
        for k in Edge[vn]:
            df = k>>geta
            vf = k^(df<<geta)
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, ((dn + df)<<geta)+vf)
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 64
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append(d<<geta|v)
    Edge[v].append(d<<geta|u)
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for k in Edge[i]:
        cost = k>>geta
        vf = k^(cost<<geta)
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

from heapq import heappop as hpp, heappush as hp
def dijkstra(N, s, Edge):
    inf = geta
    dist = [inf] * N
    dist[s] = 0
    Q = [(0, s)]
    dp = [0]*N
    dp[s] = 1
    while Q:
        dn, vn = hpp(Q)
        if dn > dist[vn]:
            continue
        for df, vf in Edge[vn]:
            if dist[vn] + df < dist[vf]:
                dist[vf] = dist[vn] + df
                dp[vf] = dp[vn]
                hp(Q, (dn + df,vf))
            elif dist[vn] + df == dist[vf]:
                dp[vf] = (dp[vf] + dp[vn]) % MOD
    return dist, dp

MOD = 10**9+7
N, M = map(int, readline().split())
S, T = map(int, readline().split())
S -= 1
T -= 1

geta = 10**15
Edge = [[] for _ in range(N)]
for _ in range(M):
    u, v, d = map(int, readline().split())
    u -= 1
    v -= 1
    Edge[u].append((d, v))
    Edge[v].append((d, u))
    

dists, dps = dijkstra(N, S, Edge)
distt, dpt = dijkstra(N, T, Edge)
st = dists[T]

onpath = [i for i in range(N) if dists[i] + distt[i] == st]

ans = dps[T]**2%MOD
for i in onpath:
    if 2*dists[i] == 2*distt[i] == st:
        ans = (ans - pow(dps[i]*dpt[i], 2, MOD))%MOD
    
    for cost, vf in Edge[i]:
        if dists[i] + cost + distt[vf] == st:
            if 2*dists[i] < st < 2*dists[vf]:
                ans = (ans - pow(dps[i]*dpt[vf], 2, MOD))%MOD
print(ans)
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

point_arr = np.zeros((H, W))

x = 0
start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            point_arr[y, start:stop] += stop - start
            start = stop + 1
    point_arr[y, start:W] += W - start
    
#print(point_arr)

for x in range(W):
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            point_arr[start:stop, x] += stop - start
            start = stop + 1
    point_arr[start:H, x] += H - start

print(int(np.max(point_arr))-1)

### FIXED CODE ###

#   ABC129　D問題
H, W = map(int, input().split())    #   1 <= H, W <= 2000
S_arr = []
for _ in range(H):
    S_arr.append(list(input()))

point_arr = [[0]*W for _ in range(H)]

start = 0
stop = W
for y in range(H):
    start = 0
    stop = W
    for x in range(W):
        if S_arr[y][x] == "#":
            stop = x
            for i in range(start, stop):
                point_arr[y][i] += stop - start
            start = stop + 1
    for i in range(start, W):
        point_arr[y][i] += W - start


for x in range(W):  #   コードのコピペ禁止の原則に違反してるけど、改善方法が思いつかない問題
    start = 0
    stop = H
    for y in range(H):
        if S_arr[y][x] == "#":
            stop = y
            for i in range(start, stop):
                point_arr[i][x] += stop - start
            start = stop + 1
    for i in range(start, H):
        point_arr[i][x] += H - start

ans = 0
for i in range(H):
    for j in range(W):
        if ans < point_arr[i][j]:
            ans = point_arr[i][j]
ans -= 1
print(ans)
#   O(H*W)程度の計算量で十分高速だと思ってたのに、そうでもない問題
#   2019/06/10 現在未解決　PyPy使ったらどうなるのかやってみた。Numpy含まれてるからランタイムエラーになるのだろうか？
### BUGGY CODE ###

n, m = map(int, input().split())
infty = int(1E9)
d = [[infty for i in range(n)] for j in range(n)]
edges = []

for i in range(n):
  d[i][i] = 0

for _ in range(m):
  x, y, c = map(int, input().split())
  x -= 1; y -= 1
  edges.append((x, y, c))
  d[x][y] = d[y][x] = c

for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for e in edges:
  x, y, c = e;
  need = False
  for i in range(n):
    for j in range(n):
      if d[i][j] == d[i][x] + d[j][y] + c:
        need = True
        break
  ans += not need

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
infty = int(1E9)
d = [[infty for i in range(n)] for j in range(n)]
edges = []

for i in range(n):
  d[i][i] = 0

for _ in range(m):
  x, y, c = map(int, input().split())
  x -= 1; y -= 1
  edges.append((x, y, c))
  d[x][y] = d[y][x] = c

for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for e in edges:
  x, y, c = e;
  need = False
  for i in range(n):
    for j in range(n):
      if d[i][j] == d[i][x] + d[j][y] + c:
        need = True
        break
  ans += not need

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

S = input()[::-1]
L = len(S)
ans = 0
now = 0
A = [0] * 2019
A[0] = 1
d = 0
for i in range(L):
    now = now + int(S[i]) * 10**d
    now %= 2019
    d += 1
    A[now] += 1

for i in A:
    ans += i * (i-1) // 2

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)
### BUGGY CODE ###

from math import ceil
x=int(input())
i=0
ok=True
if x<=2:
  print(2)
elif x==3:
  print(3)
elif x==4:
  print(5)
else:
  while 1:
    for j in range(2,ceil((x+i)**0.5)):
      if (x+i)%j==0:
        ok=False
    if ok:
      print(x+i)
      exit()
    i+=1


### FIXED CODE ###

from math import ceil
x=int(input())
i=0
if x<=2:
  print(2)
elif x==3:
  print(3)
elif x==4:
  print(5)
else:
  while 1:
    ok=True
    n=ceil((x+i)**0.5)
    for j in range(2,n):
      if (x+i)%j==0:
        ok=False
        break
    if ok:
      print(x+i)
      exit()
    i+=1
### BUGGY CODE ###

mod = 998244353

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

dp = [[[0]*3 for i in range(S+1)] for j in range(N+1)]

dp[0][0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        dp[i+1][j][2] %= mod

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

print(dp[N][S][2])

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N+1)]
dp1 = [[0]*(S+1) for _ in range(N+1)]
dp2 = [[0]*(S+1) for _ in range(N+1)]
###dp[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


dp0[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp0[i+1][j] += dp0[i][j]
        dp0[i+1][j] %= mod

        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp1[i+1][j] %= mod

        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        dp2[i+1][j] %= mod

        if j+A[i] <= S:
            dp1[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+A[i]] %= mod
        
            dp2[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+A[i]] %= mod

print(dp2[N][S])
### BUGGY CODE ###

import math
import sys
from functools import reduce
input = sys.stdin.readline

def main():
    A, B, K = map(int, input().split())

    for i in range(A, B+1):
        if i - A < K or B - i < K:
            print(i)

main()

### FIXED CODE ###

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

def it():
    for i in range(a, min(a+k, b)):
        yield i

    for i in range(max(b-k+1, a), b+1):
        yield i

for i in sorted(set(it())):
    print(i)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
ax = [int(_) for _ in input().split()]
ay = [int(_) for _ in input().split()]
az = [int(_) for _ in input().split()]
ax.sort(reverse=True)
ay.sort(reverse=True)
az.sort(reverse=True)
INF = - 3 *10 ** 10
ax.extend([INF])
ay.extend([INF])
az.extend([INF])
l = [(ax[0]+ay[0]+az[0],0,0,0)]
for i in range(k):
    t = l.pop(0)
    print(t[0])
    if (ax[t[1]+1]+ay[t[2]]+az[t[3]],t[1]+1,t[2],t[3]) not in l:
        l.append((ax[t[1]+1]+ay[t[2]]+az[t[3]],t[1]+1,t[2],t[3]))
    if (ax[t[1]]+ay[t[2]+1]+az[t[3]],t[1],t[2]+1,t[3]) not in l:
        l.append((ax[t[1]]+ay[t[2]+1]+az[t[3]],t[1],t[2]+1,t[3]))    
    if (ax[t[1]]+ay[t[2]]+az[t[3]+1],t[1],t[2],t[3]+1) not in l:
        l.append((ax[t[1]]+ay[t[2]]+az[t[3]+1],t[1],t[2],t[3]+1))
    l.sort(key=lambda x:(-x[0],x[1],x[2],x[3]))

### FIXED CODE ###

import heapq
x,y,z,k = map(int,input().split())
ax = [int(_) for _ in input().split()]
ay = [int(_) for _ in input().split()]
az = [int(_) for _ in input().split()]
ax.sort(reverse=True)
ay.sort(reverse=True)
az.sort(reverse=True)
INF = - 3 *10 ** 10
ax.extend([INF])
ay.extend([INF])
az.extend([INF])
l = [(-(ax[0]+ay[0]+az[0]),0,0,0)]
checked = {(-(ax[0]+ay[0]+az[0]),0,0,0)}
for i in range(k):
    t = heapq.heappop(l)
    print(-t[0])
    if (-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3]) not in checked:
        heapq.heappush(l,(-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3])) 
        checked.add((-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3]))
    if (-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]) not in checked:
        heapq.heappush(l,(-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]))
        checked.add((-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]))
    if (-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1) not in checked:
        heapq.heappush(l,(-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1))
        checked.add((-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1))
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

res = []
cnt = 0
i = 0
while True:
    cnt += 1
    i = a[i]-1
    if i in res:
        print(-1)
        break
    if i == 1:
        print(cnt)
        break
    else:
        res.append(i)
        

### FIXED CODE ###

n = int(input())
a = [None]
for j in range(n):
    a.append(int(input()))

i = 1
c = 0
r = [1]
while True:
    c += 1
    i = a[i]
    if i == 2:
        print(c)
        break
    if c > (10**5):
        print(-1)
        break
### 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)

kouho = set()
done = set()


def f(t):
    x, y, z = t
    return A[x] + B[y] + C[z]


def main():
    kouho.add((0, 0, 0))

    for k in range(K):
        temp = 0
        for d in (kouho - done):
            if f(d) > temp:
                todel = d
                temp = f(d)

        x, y, z = todel
        toadd = [(x, y, z+1), (x, y+1, z), (x+1, y, z)]
        for ta in toadd:
            if ta[0] == X:
                continue
            if ta[1] == Y:
                continue
            if ta[2] == Z:
                continue
            kouho.add(ta)

        done.add(todel)
        print(temp)


if __name__ == '__main__':
    main()


### 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)

kouho = set()
done = set()


def f(t):
    x, y, z = t
    if x >= X or y >= Y or z >= Z:
        return 0
    return A[x] + B[y] + C[z]


def main():
    start = (f((0, 0, 0)), (0, 0, 0))
    kouho.add(start)
    done.add(start)

    for k in range(K):
        d = max(kouho)
        kouho.remove(d)

        x, y, z = d[1]
        toadd = [(x, y, z+1), (x, y+1, z), (x+1, y, z)]
        for ta in toadd:
            t = (f(ta), ta)
            if t in done:
                continue
            kouho.add(t)
            done.add(t)

        print(d[0])


if __name__ == '__main__':
    main()