Harryxun/sft_time huggingface dataset:
### 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)

max_k_list = []
for a_i in range(X):
    for b_i in range(Y):
        for c_i in range(Z):
            if (a_i + 1) * (b_i + 1) * (c_i + 1) <= K:
                max_k_list.append(a_list[a_i] + b_list[b_i] + c_list[c_i])

max_k_list.sort(reverse = True)
[print(k) for k in max_k_list[:K]]


### FIXED CODE ###

import heapq

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)

heap = []
heapq.heappush(heap, (-(a_list[0] + b_list[0] + c_list[0]), 0, 0, 0))
searched = []
result = [0] * K

for k in range(K):
    elem = heapq.heappop(heap)
    result[k] = - elem[0]

    if elem[1] + 1 <= X - 1:
        a_next = (-(a_list[elem[1] + 1] + b_list[elem[2]] + c_list[elem[3]]), elem[1] + 1, elem[2], elem[3])
        if not a_next in searched:
            heapq.heappush(heap, a_next)
            searched.append(a_next)

    if elem[2] + 1 <= Y - 1:
        b_next = (-(a_list[elem[1]] + b_list[elem[2] + 1] + c_list[elem[3]]), elem[1], elem[2] + 1, elem[3])
        if not b_next in searched:
            heapq.heappush(heap, b_next)
            searched.append(b_next)

    if elem[3] + 1 <= Z - 1:
        c_next = (-(a_list[elem[1]] + b_list[elem[2]] + c_list[elem[3] + 1]), elem[1], elem[2], elem[3] + 1)
        if not c_next in searched:
            heapq.heappush(heap, c_next)
            searched.append(c_next)

[print(k) for k in result]
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))

maximum = 0
cnt = 0

for i in range(len(H)):
    k = H[i]
    res = H[i+1:]
    for j in res:
        if(j <= k):
            cnt += 1
            k = j
        else:
            break
        maximum = max(maximum,cnt)
        #if(max < cnt):
        #    max = cnt
    cnt = 0

print(maximum)

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))

ans = 0
tmp = 0

for i in range(N-1):
    if(H[i] < H[i+1]):
        #ans = max(ans,tmp)
        tmp = 0
    else:
        tmp += 1
    ans = max(ans,tmp)

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

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0

for i in range(n):
    num = tmp + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari[tmp]+=1



ans = 0
for key,val in amari.items():
    if val>1:
        ans += val*(val-1)//2
print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

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

sin = input()
arr = []
for s in sin:
    if len(arr)>0 and arr[-1] != s:
        arr = arr[:-1]
    else:
        arr.append(s)
print(len(sin)-len(arr))

### FIXED CODE ###

from collections import deque
sin = input()
queue = deque(maxlen=len(sin))
for s in sin:
    if len(queue)>0 and queue[-1] != s:
        queue.pop()
    else:
        queue.append(s)
#print("".join(arr))
print(len(sin)-len(queue))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
max = max(A)
list = []
x = 0
for b in range(-max,max):
    for i in range(N):
        x = x + abs(A[i]-(b+i))
    list.append(x)
    x = 0
print(min(list))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] - i - 1
A = sorted(A)
medN = N//2

x = 0
for i in range(N):
    x = x + abs(A[i] - A[medN])
print(x)
### BUGGY CODE ###

n, a, b = map(int,input().rstrip().split())
fac = [1]
for i in range(1,n+1):
    fac.append(fac[i-1]*i)
ans = 0
for i in [i for i in range(1,n+1) if (i!=a) if (i!=b)]:
    ans += fac[n]//fac[i]//fac[n-i]
print(ans)

### FIXED CODE ###

MOD = 1_000_000_007
def calc_combi(n,k):
    frac=1
    denomi=1
    for i in range(n-k+1,n+1):
        frac=frac*i%MOD
    for i in range(1,k+1):
        denomi=denomi*i%MOD
    return frac*pow(denomi,MOD-2,MOD)

n, a, b = map(int,input().rstrip().split())
nca = calc_combi(n,a)
ncb = calc_combi(n,b)
print((pow(2,n,MOD)-1-nca-ncb)%MOD)
### BUGGY CODE ###

m = int(input())
cnt = 0  ; d0 = 0 
for _ in range(m):
    d, c = map(int, input().split())
    for i in range(c):
        w = d0 + d
        if w > 9:
            d0 = w - 9
            cnt += 2
        else:
            d0 = w
            cnt += 1
print(cnt-1)


### FIXED CODE ###

mat = [[[0, 0]]*10 for _ in range(10)]
def dsr(i):
    x, cnt = 0, 0
    for j in range(10):
        w = x + i
        if w > 9:
            x = w - 9
            cnt += 2
        else:
            x = w
            cnt += 1
        mat[i][j] = [x, cnt-1]
    #mat[i][0][0] = mat[i][9][0]
    x0 = mat[i][9][1] - mat[i][8][1]   #; print('x0', x0)
    for j in range(10):
        mat[i][j][1] += x0 

for i in range(10):
    dsr(i)
#print2(mat)

m = int(input())
cnt = 0; x0 = 0   
for _ in range(m):
    d, c = map(int, input().split())
    q, r = divmod(c-1, 9)
    cnt += mat[d][8][1]*q + mat[d][r][1] - mat[d][0][1] 
    x = mat[d][r][0]
    #print('x, cnt', x, cnt)
    w = x0 + x
    if w > 9:
        x0 = w - 9
        cnt += 2
    else:
        x0 = w
        cnt += 1
    #print('x0, x, cnt', x0, x,  cnt)    
print(cnt-1)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
c=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]+l[j]>l[k] and l[i]+l[k]>l[j] and l[j]+l[k]>l[i]:
        c+=1
print(c)        
      

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
c=0
for i in range(n-2):
  for j in range(i+1,n-1):
    u=l[i]-l[j]
    if l[j+1]<=u:
      break
    ok=j+1
    ng=n
    while ng-ok>1:
      center=(ok+ng)//2
      if l[center]>u:
        ok=center
      else:
        ng=center
    c+=ng-j-1
print(c)
### BUGGY CODE ###

S = str(input())
s = len(S)
cnt = 0
A = []
for i in range(s):
  x = int(S[i:])%2019
  A.append(x)
  y = A.count(x)
  if y >= 2:
    cnt += y-1

cnt += A.count(0)
print(cnt)

### FIXED CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

print(cnt)
### BUGGY CODE ###

import itertools

A, B, C, K = map(int, input().split(" "))
data = [1 for _ in range(A)] + [0 for _ in range(B)] + [-1 for _ in range(C)]

sums = [sum(conb) for conb in itertools.combinations(data, K)]
print(max(sums))


### FIXED CODE ###

A, B, C, K = map(int, input().split(" "))
if K-A <= 0:
    print(K)
else:
    if K - (A + B) <= 0:
        print(A)
    elif K == A+B+C:
        print(A-C)
    else:
        print(A - (K-(A+B)))
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def c2(d):
    return d*(d+1)//2
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = c2(N)
    for i in range(N):
        cnt = [0]*N
        vis = [0]*N
        s = [[0, 0]]
        vis[0] += 1
        while len(s) > 0:
            v, x = s.pop()
            if c[v] != i+1:
                cnt[x] += 1
            for j in ab[v]:
                if vis[j] == 0:
                    if c[v] == i+1:
                        x += 1
                    s.append([j, x])
                    vis[j] += 1
        print(tot-sum(map(c2, cnt)))
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [0]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    sl = Bit(N)
    for i in range(1, N+1):
        sl.add(i, 1)
    for i in range(N):
        his = []
        ans = tot
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sl.sum(ol[j])-sl.sum(il[j]-1)
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl.add(il[v], -n)
            his.append([il[v], n])
        tmp = sl.sum(ol[0])-sl.sum(0)
        ans -= tmp*(tmp+1)//2
        for h in his:
            sl.add(h[0], h[1])
        print(ans)
resolve()
### BUGGY CODE ###

#!/usr/bin/env python3

import numpy as np


def solve(H, W, S):
    grid = np.zeros(H*W, dtype=np.int)
    for y in range(H):
        count = 0
        start = 0
        yw = y * W
        for x in range(W):
            if S[y][x] == '#':
                grid[yw+start:yw+x] = count
                start = x + 1
                count = 0
            else:
                count += 1
        grid[yw+start:yw+W] = count

    ans = 1
    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                for i in range(start, y):
                    if ans < grid[i*W+x] + count:
                        ans = grid[i*W+x] + count
                start = y + 1
                count = 0
            else:
                count += 1
        for i in range(start, H):
            if ans < grid[i*W+x] + count:
                ans = grid[i*W+x] + count

    return ans - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3


def solve(H, W, S):
    grid = [[0] * W for _ in range(H)]
    for y in range(H):
        count = 0
        start = 0
        for x in range(W):
            if S[y][x] == '#':
                for i in range(start, x):
                    grid[y][i] = count
                start = x + 1
                count = 0
            else:
                count += 1
        for i in range(start, W):
            grid[y][i] = count

    for x in range(W):
        count = 0
        start = 0
        for y in range(H):
            if S[y][x] == '#':
                for i in range(start, y):
                    grid[i][x] += count
                start = y + 1
                count = 0
            else:
                count += 1
        for i in range(start, H):
            grid[i][x] += count

    ans = 0
    for x in range(W):
        for y in range(H):
            if grid[y][x] > ans:
                ans = grid[y][x]
    return ans - 1


if __name__ == '__main__':
    H, W = map(int, input().split())
    S = [input().strip() for _ in range(H)]

    ans = solve(H, W, S)

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

from collections import defaultdict

H, N = map(int, input().split())
magics = defaultdict(int)

for _ in range(N):
    a, b = map(int, input().split())
    for i in range(1, H // a + 2):
        if b * i < magics[a * i] or magics[a * i] == 0:
            magics[a * i] = b * i

M = len(magics)

dp = [float('inf') for _ in range(H + 1)]
dp[0] = 0

for h in range(H + 1):
    for a, b in magics.items():
        dp[h] = min(dp[h], dp[max(h - a, 0)] + b)

print(dp[H])


### FIXED CODE ###

import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])
### BUGGY CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]
for idx in range(1, N+1):
    i = 0
    tmp = 0
    while i < len(A)-1:
        if idx == i+1:
            tmp += abs(A[i]-A[i+2])
            i += 2
        else:
            tmp += abs(A[i]-A[i+1])
            i += 1
    print(tmp)


### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]
S = sum(abs(A[i]-A[i+1]) for i in range(len(A)-1))
for i in range(1, N+1):
    print(S-(abs(A[i]-A[i+1]) + abs(A[i]-A[i-1]))+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

import copy
from scipy.misc import comb
from collections import Counter

N=int(input())
A=list(map(int,input().split() ))
B=[-1]*N   #メモ化。iの時の方法の総数

f_cnt=Counter(A)
f_dic=dict(f_cnt)

for i,item in enumerate(A):
  if B[item-1]>-1:
    print(B[item-1])
  else:
    D=copy.deepcopy(f_dic)
    D[item] -= 1
    opt=0
    for item3 in D:
      if D[item3]>=2:
        opt += D[item3]*(D[item3]-1)//2
    B[item-1]=opt
    print(opt)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split() ))
from collections import Counter
d=dict(Counter(A))
#print(d)
cnt=0
for item in d:
    cnt += (d[item])*(d[item]-1)//2

#print("cnt",cnt)
   
for num in A:
    new = max(0, (d[num]-1)*(d[num]-2)//2)
    print(cnt- d[num]*(d[num]-1)//2 + new)
### BUGGY CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+pow(10, n-1, 13)*d) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+pow(10, n-1, 13)*int(S[n-1])) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

max_m = [0]*(m+1)
m_list = [[0] for _ in range(m+1)]

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

    if a <= m:
        m_list[a].append(b)

all_r = 0

for i in range(1, m+1):
    max_m[i] = max(m_list[i])

    max_ind = 1
    max_v = max_m[1]
    for j in range(2, i+1):
        if max_m[j] >= max_v:
            max_ind = j
            max_v = max_m[j]

    ind = m_list[max_ind].index(max_v)
    all_r += m_list[max_ind].pop(ind)
    if len(m_list[max_ind]) == 0:
        m_list[max_ind].append(0)

    max_m[max_ind] = max(m_list[max_ind])

print(all_r)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappush, heappop


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

m_list = [[] for _ in range(m+1)]

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

    if a <= m:
        m_list[a].append(b)


all_r = 0
hq = []

for i in range(1, m+1):
    for v in m_list[i]:
        heappush(hq, -1*v)

    if len(hq) != 0:
        max_v = -1 * heappop(hq)
        all_r += max_v

print(all_r)
### BUGGY CODE ###

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

for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]<n-1:
            b[i+a[i]+1]-=1    
    f=0
    tmp=0
    for i in range(n):
        tmp+=b[i]
        a[i]=tmp
        if tmp!=n:
            f=1
    if f==0:
        break
print(*a)


### FIXED CODE ###

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

for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]<n-1:
            b[i+a[i]+1]-=1    
    f=0
    tmp=0
    for i in range(n):
        tmp+=b[i]
        a[i]=tmp
        if tmp!=n:
            f=1
    if f==0:
        break
print(*a)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(set(a))
l=[]
for i in range(len(b)):
  l.append(a.count(b[i]-1)+a.count(b[i])+a.count(b[i]+1))
print(max(l))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
for i in range(max(a)+3):
  l.append(0)
for j in range(n):
  l[a[j]+1]+=1
m=[]
for i in range(1,max(a)+2):
  m.append(l[i-1]+l[i]+l[i+1])
print(max(m))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  def f(n):
    dp = list(range(n+1))
    for a, b in zip(A, B):
      if b <= a:
        continue
      for i in range(n+1):
        if i-a >= 0:
          dp[i] = max(dp[i], dp[i-a]+b)
    return dp[n]
  m = f(n)
  A, B = B, A
  ans = f(m)
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H =defaultdict(int)
bom_W =defaultdict(int)
posision =set()
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision.add((h,w))
indx_H = [k for k,v in bom_H.items() if v == max(bom_H.values())]
indx_W = [k for k,v in bom_W.items() if v == max(bom_W.values())]
set_max_H = set(indx_H)
set_max_W = set(indx_W)
temp_H =max(bom_H.values())
temp_W =max(bom_W.values())

flag =False
for h in set_max_H:
    for w in set_max_W:
        if (h,w) not in posision:
            flag =True
            break

if flag ==True:
    print(temp_H +temp_W )
else:
    print(temp_H +temp_W -1)

### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
        # 即座に探索を終了する.
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

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

q = 1000000000000000000
b = 1
cek = True
for i in range(n):
	b = b*a[i]
if b > q :
	print("-1")
else :
	print(b)

### FIXED CODE ###

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

q = 1000000000000000000
b = 1
cek = True
zero = a.count(0)
if zero > 0 :
	print("0")
else :
	for i in range(n) :
		b = b*a[i]
		if b > q :
			cek = False
			break
	if cek :
		print(b)
	else :
		print("-1")
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n = int(input())
dists = []
for i in range(n):
    ds = map(int, input().split())
    for j, c in enumerate(ds):
        if i >= j:
            continue
        dists.append((c, i, j))
dists.sort()

uf = UnionFind(n)
links = [[0] * n for _ in range(n)]

for c, i, j in dists:
    if not uf.find(i, j):
        links[i][j] = c
        links[j][i] = c
        uf.union(i, j)
        continue
    graph = dijkstra(links, directed=False, indices=[i, j])
    if graph[0][j] < c:
        break
    elif graph[0][j] > c:
        links[i][j] = c
        links[j][i] = c

graph = dijkstra(links, directed=False)
for c, i, j in dists:
    if graph[i][j] != c:
        print(-1)
        break
else:
    print(sum(sum(l) for l in links) // 2)


### FIXED CODE ###

def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min((ik + kj for ik, kj in zip(row_i, row_j) if ik and kj), default=float('inf'))
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))
### BUGGY CODE ###

#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]
#(ord('A'))でASCII出力 Aは65
import math
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

N = intinput()
A = {}

for i in range(N):
    s = input()
    if s in A:
        A[s] += 1
    else:
        A[s] = 1

maxalist = [kv[0] for kv in A.items() if kv[1] == max(A.values())]
maxalist.sort()
for i in maxalist:
    print(i)


### FIXED CODE ###

#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]
#(ord('A'))でASCII出力 Aは65
import math
import string

def intinput():
    return int(input())

def listintinput():
    return list(map(int,input().split()))

def splitintinput():
    return map(int,input().split())

N = intinput()
A = {}

for i in range(N):
    s = input()
    if s in A:
        A[s] += 1
    else:
        A[s] = 1
        
j = max(A.values())

maxalist = [kv[0] for kv in A.items() if kv[1] == j]
maxalist.sort()
for i in maxalist:
    print(i)