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

import math
from functools import lru_cache


def resolve():
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = map(int, input().split())

    A = sorted(A)
    B = A[::-1]

    @lru_cache(maxsize=None)
    def permutations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    sum = 0
    for i in range(K-1, N):
        sum += permutations_count(i, K-1) * A[i] % MOD - permutations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count____(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    def combinations_count_(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    def combinations_count(n, r, mod=10**9+7):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod
    
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


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

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            if c1 == c2:
                match = 1
            else:
                match = 0
            pr2 = results[j]
            mval = max(sec1, pr2, pr1 + match)
            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]



n = int(input())
s = []
for line in sys.stdin:
    s.append(line.strip())
for i in range(0, 2*n, 2):
    print(len_lcs(s[i], s[i+1]))





### FIXED CODE ###

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()
### BUGGY CODE ###

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

maximum = max(A)
for i in range(N):
    if A[i] != maximum:
        print(maximum)
    else:
        num = A[i]
        A[i] = 0
        print(max(A))
        A[i] = num
        

### FIXED CODE ###

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

maximum = max(A)
count_max = A.count(maximum)
if count_max > 1:
    for i in range(N):
        print(maximum)
else:
    for i in range(N):
        if A[i] != maximum:
            print(maximum)
        else:
            num = A[i]
            A[i] = 0
            print(max(A))
            A[i] = num
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())
while n:
    l = list()
    for _ in range(n):
        l.append(int(input()))

    maxs = 0
    for i in range(n):
        for j in range(i,n):
            s = 0
            for k in range(i,j+1):
                s += l[k]
            maxs = max(maxs,s)
    n = int(sys.stdin.readline())
    print(maxs)

### FIXED CODE ###

import sys

n = int(sys.stdin.readline())
while n:
    l = list()
    for _ in range(n):
        l.append(int(input()))
    a = l.copy()
    for i in range(1,n):
        a[i] = max(a[i-1] + l[i], l[i])
    print(max(a))
    n = int(sys.stdin.readline())
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=0
aa=list(set(a))

for i in aa:
    cnt=a.count(i)
    if cnt>i:
        ans+=cnt-i
    elif cnt<i:
        ans+=cnt

print(str(ans))




### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
ans=0
aa=list(set(a))
dict={}
for s in aa:
    dict[s]=0
for l in a:
    dict[l]+=1
for i in dict.items():
    num=i[0]
    amount=i[1]
    """                                                           
    cnt=a.count(i)                                                
    if cnt>i:                                                     
        ans+=cnt-i                                                
    elif cnt<i:                                                   
        ans+=cnt                                                  
    """
    if amount>num:
        ans+=amount-num
    elif amount<num:
        ans+=amount
print(str(ans))
### BUGGY CODE ###

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

sum = 0

for i in range(1,len(li)):
    if max(li[:i]) > li[i]:
        sum += max(li[:i]) - li[i]

print(sum)

### FIXED CODE ###

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

sum = 0

for i in range(len(li)-1):
    if li[i] > li[i+1]:
        sum += li[i] - li[i+1]
        li[i+1] = li[i]

print(sum)
### BUGGY CODE ###

n, h = map(int, input().split())
list_w = []
max_a = [-1, -1, 10**9]
for i in range(n):
  a, b = list(map(int, input().split()))
  list_w.append([a, b])
  if max_a[1] < a:
    max_a = [i, a, b]
  elif max_a[1] == a and max_a[2] > b:
    max_a = [i, a, b]  
list_w.pop(max_a[0])
list_w.sort(key=lambda x:x[1], reverse=True)

count = 0
while h > 0:
  if h > max_a[2]:
    if len(list_w) > 0 and list_w[0][1] > max_a[1]:
      h -= list_w[0][1]
      list_w.pop(0)
      count += 1
    else:
      if max_a[2] > max_a[1]:
        num = (h - max_a[2]) // max_a[1]
        h -= max_a[1] * num
        count += num
      else:
        num = h // max_a[1]
        h -= max_a[1] * num
        count += num
  else:
    h -= max_a[2]
    count += 1
print(count)

### FIXED CODE ###

import math
n, h = map(int, input().split())
list_a = []
list_b = []
for i in range(n):
  a, b = list(map(int, input().split()))
  list_a.append(a)
  list_b.append(b)
max_a = max(list_a)
use_b = [b for b in list_b if b > max_a]
use_b.sort(reverse=True)

count = 0
while h > 0:
  if len(use_b) > 0:
    h -= use_b.pop(0)
    count += 1
  else:
    count += math.ceil(h / max_a)
    break
print(count)
### BUGGY CODE ###

n,x,y = map(int,input().split())
x,y = x-1,y-1

D = {}
for i in range(n):
    D[str(i+1)]=0
    
for i in range(n-1):
    for j in range(i+1,n):
        dist1 = j-i
        dist2 = abs(i-x) +1 + abs(j-y)
        dist = min(dist1,dist2)
        D[str(dist)] = D[str(dist)]+1


    
for i in range(1,n):
    print(D[str(i)])

### FIXED CODE ###

n,x,y = map(int,input().split())
x,y = x-1,y-1

D = [0 for _ in range(n+1)]
    
for i in range(n-1):
    for j in range(i+1,n):
        dist1 = j-i
        dist2 = abs(i-x) +1 + abs(j-y)
        dist = min(dist1,dist2)
        D[dist] = D[dist]+1


    
for i in range(1,n):
    print(D[i])
### BUGGY CODE ###

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

result = 0

if n <= 2:
    print(0)
else:
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                    if j-i != k-j:
                        result +=1
print(result)

### FIXED CODE ###

n = int(input())
s = input()
 
result = 0
 
if n <= 2:
    print(0)

for i in range(n-2):
    if s[i] == "R":
        a = s[i+1:].count("G")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "G" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "G"):
                result -= 1
    elif s[i] == "G":
        a = s[i+1:].count("R")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "R"):
                result -= 1
    elif s[i] == "B":
        a = s[i+1:].count("R")
        b = s[i+1:].count("G")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "G") or (s[i+j] == "G" and s[i+2*j] == "R"):
                result -= 1
print(result)
### BUGGY CODE ###

n,m = map(int,raw_input().split())
keys = []
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	keys.append((mask,a))

dp = []
M = 1<<n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		k = j|keys[i][0]
		dp[i+1][k] = min(dp[i+1][k], dp[i][j]+keys[i][1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
 
if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

### FIXED CODE ###

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

M = 1<<n
dp = [10**9]*M
dp[0] = 0
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	for j in xrange(M):
		dp[j|mask] = min(dp[j|mask], dp[j]+a)
	#print dp
 
if dp[M-1] >= 10**9:
	print -1
else:
	print dp[M-1]
### BUGGY CODE ###

import math
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)

while M > 0:
  A[0] = A[0]/2
  A.sort(reverse = True)
  M -= 1

A = list(map(math.floor, A))
print(sum(A))

### FIXED CODE ###

import math
import bisect

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

def XX(A, M):
  if M <= 0 or A[0]<1:
    return
  A[0] = A[0]/2
  M -= 1
  for i in range(1, len(A)):
    if A[i] > A[0] and M > 0:
      A[i] = A[i]/2
      M -= 1
    else:
      break
  A.sort(reverse = True)
  XX(A, M)
  
XX(A, M)
A = list(map(math.floor, A))
print(sum(A))
### BUGGY CODE ###

s = input()
l = len(s)
mod = 10**9 + 7

# dp[i][j] = 上からi桁目まで見た時のjと合同な数の個数
dp =[[0]*13 for _ in range(l+1)]
dp[0][0] = 1
for i in range(l):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
print(dp[l][5]%mod)


### FIXED CODE ###

s = input()
l = len(s)
mod = 10**9 + 7

# dp[i][j] = 上からi桁目まで見た時のjと合同な数の個数
dp =[[0]*13 for _ in range(l+1)]
dp[0][0] = 1
for i in range(l):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
print(dp[l][5]%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(m):
    a = A.pop() / 2
    bisect.insort(A, a)
ans = 0
for a in A:
    ans += a // 1
print(int(ans))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
A = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(A)
for _ in range(m):
    tmp = heapq.heappop(A)
    tmp = int((-tmp / 2) // 1)
    heapq.heappush(A, -tmp)
print(-sum(A))
### BUGGY CODE ###

a = input()
b = input()
c = input()


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = {i: True for i in range(-10000, 10001)}
    for i in range(len(s)):
        for j in range(len(t)):
            if not comp(s[i], t[j]):
                check_st[i - j] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx] and check_ac[c_idx] and check_bc[c_idx - b_idx]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)


### FIXED CODE ###

a = input()
b = input()
c = input()

OFFSETS = 9000


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = [True] * (OFFSETS * 2 + 10)
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j + OFFSETS] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx + OFFSETS] and check_ac[
                c_idx + OFFSETS] and check_bc[c_idx - b_idx + OFFSETS]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)
### BUGGY 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()

ans = 0

for i in range(N):
  if A[0] >= B[i]:
    continue
  if A[N-1] < B[i]:
    a = N
  else:
    left = 0
    right = N-1
    while right - left > 1:
      mid = (left + right) // 2
      if  B[i]> A[mid]:
        left = mid
      else:
        right = mid
    a = left + 1
  if C[N-1] <= B[i]:
    continue
  if C[0] > B[i]:
    c = N
  else:      
    left = 0
    right = N-1
    while right - left > 1:
      mid = (left + right) // 2
      if B[i]>= C[mid]:
        left = mid
      else:
        right = mid
    c = len(C[right:])
  ans += a*c
print(ans)


### FIXED CODE ###

import bisect as bi
def main():
  from builtins import input, int, map
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  C = list(map(int,input().split()))
  A.sort()
  C.sort()

  ans = 0

  for i in range(N):
    a = bi.bisect_left(A,B[i])
    c = N-bi.bisect_right(C,B[i])
    ans += a*c
  print(ans)
main()
### BUGGY CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999

def dfs(bx, s, v):
  ddprint("dfs bx {} s {} v {}".format(bx,s,v))
  if s == fff:
    if v<dp[fff]:
      dp[fff] = v
    return dp[fff]
  if bx>=n:
    return BIG
  if v>=dp[s]:
    return dp[fff]
  bit = (1<<bx)
  if bit|s == s:
    return dfs(bx+1,s,v)
  mn = BIG
  for z in box[bx]:
    val = z[1]
    addset = z[2]
    ddprint("call newi {} newset {} newv {}".format(i+1, s|addset, v+val))
    newval = dfs(bx+1, s|addset, v+val)
    mn = min(mn, newval)
  return mn

# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
key = []
box = [ [] for i in range(n) ]
for i in range(m):
  a,b = inm()
  c = inl()
  s = 0
  c = [x-1 for x in c]
  for cc in c:
    s |= (1<<cc)
  v = a/len(c)
  key.append((v,a,b,c,s))
  for bx in c:
    box[bx].append((v,a,s,i))  # prio,val,set,suf

for z in box:
  z.sort()
  ddprint(z)

v = dfs(0,0,0)
print(-1 if v>=BIG else v)


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999


# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
a = []
s = []
for i in range(m):
  aa,bb = inm()
  c = inl()
  ss = 0
  c = [x-1 for x in c]
  for cc in c:
    ss |= (1<<cc)
  a.append(aa)
  s.append(ss)

dp = [BIG] * (2**n)
dp[0] = 0

for i in range(m):
  aa = a[i]
  ss = s[i]
  for j in range(2**n):
    dp[j|ss] = min(dp[j|ss], dp[j]+aa)

v = dp[2**n-1]
print(-1 if v>=BIG else v)
### BUGGY CODE ###

N=int(input())
cost=[[float("inf")]*N for _ in range(N)]
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
    cost[a][b]=c
    cost[b][a]=c

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
        
    return d

Q,K=map(int,input().split())
K-=1
d=dijkstra(K,cost)
for _ in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N=int(input())
graph=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append([b,c])
    graph[b].append([a,c])

def dfs(start):
    for x,cost in graph[start]:
        if d[x]==-1:
            d[x]=d[start]+cost
            dfs(x)

Q,K=map(int,input().split())
K-=1
d=[-1]*N
d[K]=0
dfs(K)
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(d[x]+d[y])
### BUGGY CODE ###

from collections import Counter

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

s = Counter(c)
t = list(s.items())

nag = len(t)
x = 0
ans = 0

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
    
for j in range(n):
    hg = c.count(c[j])
    ans = x - (hg-1)
    print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
c = list(map(int,input().split()))
s = Counter(c)
t = list(s.items())
nag = len(t)
x = 0
ans = 0

for i in range(nag):
    x += (t[i][1]*(t[i][1]-1))//2
    
for j in range(n):
    ans = x - s[c[j]] + 1 
    print(ans)
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
count = 0
for k in range(1, 10**5):
    min = sum(x<k for x in d)
    max = sum(x>=k for x in d)
    if min == max:
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
d = sorted(d)
length = len(d) // 2
max = d[length]
min = d[length - 1]
print(max - min)
### BUGGY CODE ###

from sys import stdout

s = input()
q = int(input())
order = 1
for i in range (q):
  e = input().split()
  if e[0] == '1':
    order *= (-1)
  else:
    if order == 1:
      if e[1] == '1':
        s = e[2] + s
      else:
        s += e[2]
    else:
      if e[1] == '2':
        s = e[2] + s
      else:
        s += e[2]
stdout.write(s if order == 1 else s[::-1])

### FIXED CODE ###

from sys import stdout

s = input()
q = int(input())
pref = ''
suff = ''
order = 1
for i in range (q):
  e = input().split()
  if e[0] == '1':
    order *= (-1)
  else:
    if order == 1:
      if e[1] == '1':
        pref = e[2] + pref
      else:
        suff += e[2]
    else:
      if e[1] == '2':
        pref = e[2] + pref
      else:
        suff += e[2]
if order == 1:
    stdout.write(pref)
    stdout.write(s)
    stdout.write(suff)
else:
    stdout.write(suff[::-1])
    stdout.write(s[::-1])
    stdout.write(pref[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
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])
count=0
for edge in range(m):
  flag=False
  for j in range(n):
    for k in range(n):
      if d[j][a[edge]]+c[edge]+d[b[edge]][k]==d[j][k]:
        flag=True
        break
    if flag:
      break
  else:
    count+=1
print(count)

### FIXED CODE ###

import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(d)
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])
count=0
for i in range(n):
  for j in range(i):
    if d2[i][j] != 100000 and d[i][j]!=d2[i][j]:
      count+=1
print(count)
### BUGGY CODE ###

n = int(input())

a = list(int(i) for i in input().split(" "))

prod = 1

for i in a:
  prod *= i

if prod > (10 ** 18):
  prod = -1

print(prod)

### FIXED CODE ###

n = int(input())

a = list(int(i) for i in input().split(" "))

prod = 1

if 0 in a:
  prod = 0
else:
  for i in a:
    prod *= i
    if prod > (10 ** 18):
      prod = -1
      break


print(prod)
### BUGGY CODE ###

N = int(input())
S = list(input() for _ in range(N))

a = sorted(list(set(S)))
b = [0] * len(a)
for i in range(N):
  b[a.index(S[i])] += 1
  
for j in range(len(a)):
  if b[j] == max(b):
    print(a[j])

### FIXED CODE ###

N = int(input())
S = list(input() for _ in range(N))

import collections
a = collections.Counter(S).most_common()
ans = []
for i in range(len(a)):
  if i == 0:
    ans.append(a[i][0])
  elif a[i - 1][1] == a[i][1]:
    ans.append(a[i][0])
  else:
    break
ans.sort()

for j in ans:
  print(j)