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

import sys
input=sys.stdin.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)



### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#d=np.array(d,np.int64)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

sys.setrecursionlimit(100000)

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

def f(x, n):
    if x == 0 or x == n:
        return 0
    debug(x,n)
    # if 2*x == n:
    #     return 3*x
    if x % (n-x) == 0:
        return 3*x
    if 2*x < n:
        return f(x, n-x) + 3*x# n + x
    a = x//(n-x) + 1
    t = a*(n-x) - x
    return f(n-x-t, n-x) + 3*x # + t

print(f(X, N))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)

sys.setrecursionlimit(100000)

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

def f(x, n):
    if x == 0 or x == n:
        return 0
    debug(x,n)
    # if 2*x == n:
    #     return 3*x
    if x % (n-x) == 0:
        return 3*x
    if 2*x < n:
        # return f(x, n-x) + 3*x# n + x
        return f(n-x, n)
    a = x//(n-x) + 1
    t = a*(n-x) - x
    return f(n-x-t, n-x) + 3*x # + t

print(f(X, N))
### BUGGY CODE ###

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

if M % N == 0:
    print(M//N)
    exit()

ans = 1
for i in reversed(range(1, (M//N)+1)):
    # 最大公約数がiとする
    rest = M - (i * N)
    if (i+rest) % i == 0:
        ans = i
        break
print(ans)

### FIXED CODE ###

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

ans = 1

for i in range(1, int(m ** 0.5)+1):
  if m % i == 0:
    if i >= n:
      ans = max(ans, m // i)
    elif m // i >= n:
      ans = max(ans, i)
      
      
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

a,b,c,d = map(int,input().split())
c_=0
d_=0
n=0
if a%c!=0 and b>c:
    c_= a+c-a%c #12
    n+=1
elif b<c:
    c_= b
else:
    c_ = a
    n+=1
if a%d!=0 and b>d:
    d_= a+d-a%d #16
    n+=1
elif b<d:
    d_= b
else:
    d_ = a
    n+=1
r = max(c,d)%min(c,d)
b_=min(c,d)
while r!=0:
    a_= b_
    b_=r
    r=a_%b_
e = int(c*d/b_)
if a%e!=0 and b>e:
    e_= a+e-a%e #48
    n-=1
elif b<e:
    e_= b
else:
    e_ = a
    n-=1
n += (b-c_)//c+(b-d_)//d-(b-e_)//e
print(1+b-a-n)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a = list(map(int,input().split()))
b = deque([])
for i in range(n):
    if i%2==0:
        b.appendleft(a[i])
    else:
        b.append(a[i])
else:
    if n%2==0:
        b = list(b)
        b = b[::-1]
print(*b)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
         
n = [1, 1]
  
for i in range(2, N+1):
    if i-2 in a:n[i-2]=0
    if i-1 in a:n[i-1]=0
    n.append(n[i-2]+n[i-1])

print(n[-1]%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

broken= [False]*(N+1)
for i in range(M):
    broken[int(input())] = True

dp = [0]*(N+1)
dp[0] = 1
if not broken[1]:dp[1] = 1

         
for i in range(2, N+1):
    if broken[i]:continue
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= (10**9 + 7)
print(dp[N])
### BUGGY CODE ###

def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
    Q = int(input())
    for q in range(Q):
        ans = 0
        le, ri = (int(i) for i in input().split())
        while le != ri:
            j, i = num_to_xy[le]
            y, x = num_to_xy[le + D]
            ans += abs(x - i) + abs(y - j)
            le += D
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


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

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
M = 10**6
def main(N, A):
    u = [False] * (M + 1)
    mx = 0
    for n in range(2, M + 1):
        if u[n]: continue
        for nn in range(n, M + 1, n):
            u[nn] = True
        c = 0
        for a in A:
            if a % n == 0:
                c += 1
        if c == N:
            print('not coprime')
            return
        mx = max(mx, c)
    if mx <= 1:
        print('pairwise coprime')
    else:
        print('setwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from math import gcd
M = 10**6
def main(N, A):
    g = 0
    for a in A:
        g = gcd(g, a)
    if g > 1:
        print('not coprime')
        return

    u = [False] * (M + 1)
    cc = [0] * (M + 1)
    for a in A:
        cc[a] += 1
    for n in range(2, M + 1):
        if u[n]: continue
        c = 0
        for nn in range(n, M + 1, n):
            u[nn] = True
            c += cc[nn]
        if c >= 2:
            print('setwise coprime')
            return
    print('pairwise coprime')

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0]*(w+1)
for i in range(n):
    for j in range(w,wv[i][0]-1,-1):
        dp[j] = max(dp[j],dp[j-wv[i][0]]+wv[i][1])

print(max(dp))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,w = map(int,input().split())
wv = [tuple(map(int,input().split())) for i in range(n)]

dp = [0]*(w+1)
for i in range(n):
    for j in range(w,wv[i][0]-1,-1):
        dp[j] = max(dp[j],dp[j-wv[i][0]]+wv[i][1])

print(max(dp))
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = map(int, input().split())
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]
ans = 0
for i in range(W + 1):
    ans = max(ans, dp[N][i])
print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(N+1)]

for j in range(N):
    w, v = map(int, input().split())
    for k in range(W + 1):
        if k >= w:
            dp[j+1][k] = max(dp[j][k-w] + v, dp[j][k])
        else:
            dp[j+1][k] = dp[j][k]

print(dp[N][W])
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1
cw+=1
dh+=1
dw+=1
ans[ch][cw] = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
move2 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        move2.append((i, j))
q = deque()
one_time = deque()
q.append([ch, cw])
while q:
    x, y = q.popleft()
    one_time.append((x, y))
    for (i, j) in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append((v1, v2))
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for (i, j) in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append((v1, v2))
print(ans[dh][dw])

### FIXED CODE ###

from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 10**15
for i in range(1,n):
    x = abs(sum(a[:i]) - sum(a[i:]))
    ans = min(ans,x)
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])
a_c = a.cumsum()
a_t = a_c[-1]
diff = np.abs(2 * a_c - a_t)
ans = diff[:-1].min()
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(N):
    j = N-i
    count = 0
    k = j
    while k<N+1:
        if k in ans:
            count += 1
        k += j
    if count%2 != a[j-1]:
        ans.append(j)
print(len(ans))
ans = [str(x) for x in ans]
ans = ' '.join(ans)
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
boxes = [0 for _ in range(N)]
ans = []
for i in range(N):
    j = N-i
    count = sum([boxes[k] for k in range(j-1,N,j)])
#    k = j*2
#    while k<N+1:
#        if k in ans:
#            count += 1
#        k += j
    if count%2 != a[j-1]:
        ans.append(j)
        boxes[j-1] = 1
print(len(ans))
ans = [str(x) for x in ans]
ans = ' '.join(ans)
print(ans)
### BUGGY CODE ###

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

gcd = gcd(a, b)
ans = 1
for i in range(2, gcd):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if ans == 1 and gcd != 1:
    ans = 2
print(ans)

### FIXED CODE ###

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

gcd = gcd(a, b)
ans = 1
n = int(gcd**0.5) + 2
for i in range(2, n):
    if gcd%i == 0:
        ans += 1
        while gcd%i == 0:
            gcd //= i
    if gcd < i:
        break
if gcd >= n:
    ans += 1
if ans == 1 and gcd != 1:
    ans = 2
    
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
res = 0
for i in r:
  for j in b:
    for k in g:
      if (i + j) / 2 != k and (j + k) / 2 != i and (k + i) / 2 != j:
        res += 1
print(res)


### FIXED CODE ###

n=int(input())
s=input()
R=[]
G={}
B=[]
for i in range(n):
  if s[i]=='R':
    R.append(i+1)
  elif s[i]=='G':
    G[i+1]=G.get(i+1,0)+1
  else:
    B.append(i+1)
res=len(R)*len(G)*len(B)
for i in R:
  for j in B:
    if ((i+j)%2==0 and G.get((i+j)//2,0)==1):
      res-=1
    if G.get(2*max(i,j)-min(i,j),0)==1:
      res-=1
    if G.get(2*min(i,j)-max(i,j),0)==1:
      res-=1
print(res)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)

#N200000
if Q>190000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

import math
from functools import reduce

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

# 整数を一つ入力
N = int(input())

res = 0

for a in range(1,N+1):
    for b in range(1,N+1):
        for c in range(1,N+1):
            res += gcd(a,b,c)

print(res)


### FIXED CODE ###

import math
from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=10000)
def gcd(*numbers):
    return reduce(math.gcd, numbers)

# 整数を一つ入力
N = int(input())

res = 0

for a in range(1,N+1):
    for b in range(1,N+1):
        gcdab = gcd(a,b)
        for c in range(1,N+1):
            res += gcd(gcdab,c)

print(res)
### BUGGY CODE ###

N = int(input())
l = [int(i) for i in input().split()]

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

if N == 2:
    print(max(l))
    exit()

p = l.pop(0)
ans = []
for j in range(1,N+1):
    element = gcd(l[0], l[1])
    for i in range(2,N-1):
        element = gcd(element,l[i])
    ans.append(element)
    l.append(p)
    p = l.pop(0)
print(max(ans))


### FIXED CODE ###

N = int(input())
l = [int(i) for i in input().split()]

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

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

p = make_divisors(l[0])
p.extend(make_divisors(l[1]))

p.sort(reverse=True)
for i in p:
    ans = 1
    flag = 0
    for j in l:
        if j%i != 0:
            if flag == 1:
                ans = 0
                break
            flag = 1
    if ans:
        print(i)
        exit()
### BUGGY CODE ###

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

i = 0
maxSum = 0
while(i<K):
  if(i<A):
    maxSum += 1
  elif(i<A+B):
    maxSum += 0
  elif(i<A+B+C):
    maxSum -= 1
  i+=1
print(maxSum)

### FIXED CODE ###

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

tmp = K
maxSum = 0
i = 0
if(tmp>A):
  maxSum+=A
  tmp-=A
else:
  maxSum+=K
  tmp = 0
#print(str(tmp) + ' sum = ' + str(maxSum))

if(tmp>B):
  tmp-=B
else:
  tmp = 0
#print(str(tmp) + ' sum = ' + str(maxSum))

if(tmp>C):
  maxSum-=C
  tmp-=C
else:
  maxSum-=tmp
  tmp = 0
#print(str(tmp) + ' sum = ' + str(maxSum))

print(maxSum)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*N
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(*A)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(1,n+1):
  power = power * i 

print(power%(10**9+7))

### FIXED CODE ###

n = int(input())

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

print(power)
### BUGGY CODE ###

import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
for i in range(n-1):
    ans = (l[i])**2%m
    if ans in l:
        b = int(np.where(l==ans)[0])
        print(np.sum(l[:b]) + np.sum(l[b:])*((n-b)//(i-b+1))+np.sum(l[b:b+(n-b)%(i-b+1)]))
        sys.exit()
    else:
        l = np.append(l,ans)
print(np.sum(l))

### FIXED CODE ###

import sys

n,x,m = (int(i) for i in input().split())
l = [x]
ans = x
memo_array = [-1]*(m+1)

for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(sum(l[:idx]) + sum(l[idx:])*(loop_num)+sum(l[idx:idx+mod]))
        sys.exit()
    l.append(ans)
    memo_array[ans]=i
print(sum(l))
### BUGGY CODE ###

import numpy as np
X, Y, Z, K, *L = map(int, open(0).read().split())
A = L[:X]
B = L[X:X+Y]
C = L[X+Y:]
ab = []
for i in range(X):
  for j in range(Y):
    ab += [A[i]+B[j]]
ab.sort()
ab = np.array(ab)
c = np.array(C)
l = -1
r = 10**30+1
M = X*Y*Z
for k in range(K):
  l = -1
  r = 10**30+1
  M = X*Y*Z
  while l+1<r:
    n = (l+r)//2
    d = n-c
    m = np.searchsorted(ab,d).sum()
    if M-m>k:
      l = n
    else:
      r = n
  print(l)

### FIXED CODE ###

inf = input().split()
X = int(inf[0])
Y = int(inf[1])
Z = int(inf[2])
K = int(inf[3])

A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ab = []
for a in A:
  for b in B:
    ab +=[a+b]
ab.sort(reverse=True)
C.sort(reverse=True)
state = [[ab[0]+C[i],0,i] for i in range(len(C))]
count  = 0
while count<K:
  s = max(state)
  print(s[0])
  count +=1
  x = s[1]
  i = s[2]
  if x<X*Y-1:
    state[i][0] = C[i]+ab[x+1]
    state[i][1] = x+1
  else:
    state[i][0] = -1
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

#print(N,A,B,C)

count=0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if A[i]<B[j]<C[k]:
                count+=1
print(count)
#do binary search



### FIXED CODE ###

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

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] > threshold:
            right = mid
        else:
            left = mid
    return right

ans = 0

BtoC = [None] * N
for i in range(0, N):
    BtoC[i] = N - binsearch(B[i], C)
#print(BtoC)

cumulative=[0]
for i in range(N):
    cumulative.append(cumulative[i] + BtoC[N-i-1])
#print(cumulative)
cumulative.reverse()
#print(cumulative)

for j in range(0, N):
    temp = binsearch(A[j], B)
    ans += cumulative[temp]

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

N = int(input())
A_list = list(map(int, input().split()))
B_list = []
for i in range(1, N):
    B_i = A_list.count(i)
    print(B_i)
print(0)


### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
ans_list = [0] * (N + 1)
for i in range(N-1):
    ans_list[A_list[i]] += 1
for j in range(N):
    print(ans_list[j + 1])
### BUGGY CODE ###

N=int(input())
ans=[]
for i in range(N):
    S=input()
    if S in ans:
        continue
    else:
        ans.append(S)
print(len(ans))

### FIXED CODE ###

N=int(input())
ans=[]
for i in range(N):
    ans.append(input())
ans_l=set(ans)

print(len(ans_l))