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

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

from collections import deque

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1
#sth,stw = list(map(int,input().split()))
#sth, stw = sth-1, stw-1
#glh, glw = list(map(int,input().split()))
#glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
#direc = [[1,0], [-1,0], [0,1], [0,-1]]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Dist[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                next_q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1
                ret = max(ret, Dist[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

from collections import deque

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

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

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

countL2R = [[0 for i in range(w)] for j in range(h)]
countR2L = [[0 for i in range(w)] for j in range(h)]
countU2D = [[0 for i in range(w)] for j in range(h)]
countD2U = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            countL2R[i][j] = -1
            countR2L[i][j] = -1
            countU2D[i][j] = -1
            countD2U[i][j] = -1

for i in range(h):
    for j in range(w):
        if j > 0 and countL2R[i][j] != -1:
                countL2R[i][j] = countL2R[i][j - 1] + 1

        j = w - j - 1
        if j < w - 1 and countR2L[i][j] != -1:
            countR2L[i][j] = countR2L[i][j + 1] + 1

        if i > 0 and countU2D[i][j] != -1:
            countU2D[i][j] = countU2D[i - 1][j] + 1

        I = i
        i = h - i - 1
        if i < h - 1 and countD2U[i][j] != -1:
            countD2U[i][j] = countD2U[i + 1][j] + 1
        i = I

ans = 0
for i in range(h):
    for j in range(w):
        if countD2U[i][j] != -1:
            ans = max(ans, countD2U[i][j] + countU2D[i][j] + countR2L[i][j] + countL2R[i][j])

print(ans + 1)


### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

countL2R = [[0 for i in range(w)] for j in range(h)]
countR2L = [[0 for i in range(w)] for j in range(h)]
countU2D = [[0 for i in range(w)] for j in range(h)]
countD2U = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            countL2R[i][j] = -1
            countR2L[i][j] = -1
            countU2D[i][j] = -1
            countD2U[i][j] = -1

for i in range(h):
    for j in range(w):
        if j > 0 and countL2R[i][j] != -1:
                countL2R[i][j] = countL2R[i][j - 1] + 1

        j = w - j - 1
        if j < w - 1 and countR2L[i][j] != -1:
            countR2L[i][j] = countR2L[i][j + 1] + 1

        if i > 0 and countU2D[i][j] != -1:
            countU2D[i][j] = countU2D[i - 1][j] + 1

        I = i
        i = h - i - 1
        if i < h - 1 and countD2U[i][j] != -1:
            countD2U[i][j] = countD2U[i + 1][j] + 1
        i = I

ans = 0
for i in range(h):
    for j in range(w):
        if countD2U[i][j] != -1:
            ans = max(ans, countD2U[i][j] + countU2D[i][j] + countR2L[i][j] + countL2R[i][j])

print(ans + 1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
saisyo = min(A)
for _ in range(M):
    b, c = map(int, input().split())
    if c > saisyo: #枝刈り
        A += [c] * b

A.sort(reverse = True)

ans = 0
for i in range(N):
    ans += A[i]

print (ans)

### FIXED CODE ###

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

cb = []
for i in A:
    cb += [[i,1]]
for _ in range(M):
    b, c = map(int, input().split())
    cb += [[c, b]]
cb.sort(reverse = True)
#print (cb)

ans = 0
i = 0
j = 0
while i <= N:
    a = min(N-i, cb[j][1])
    ans += cb[j][0] * a
    j += 1
    i += a
    #print (ans)
    if i == N:
        print (ans)
        i += 1
### BUGGY CODE ###

S = input()
Q = int(input())


flip = 0
head = ""
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            # S = c + S
            head = head + c
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            # S = c + S
            head = head + c

if (flip % 2) == 0:
    head = head[::-1]
    S = head + S
else:
    S = S[::-1]
    S = S + head

print(S)


### FIXED CODE ###

S = input()
Q = int(input())


flip = 0
head = ""
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            # S = c + S
            head = head + c
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            # S = c + S
            head = head + c

if (flip % 2) == 0:
    head = head[::-1]
    S = head + S
else:
    S = S[::-1]
    S = S + head

print(S)
### BUGGY CODE ###

from collections import deque

def pr(A,n):
    for i in range(n):
        if i!=n-1:
            print(A[i],end=" ")
        else:
            print(A[i])

n=int(input())
que_r=deque()

for i in range(n):
    s=input().split()

    if s[0]=="insert":
        que_r.appendleft(int(s[1]))
    elif s[0]=="delete":
        try:
            que_r.remove(int(s[1]))
        except: pass
    elif s[0]=="deleteFirst":
        gav=que_r.popleft()
    elif s[0]=="deleteLast":
        gav=que_r.pop()

pr(que_r,len(que_r))


### FIXED CODE ###

from collections import deque


n=int(input())
que_r=deque()

for i in range(n):
    s=input()
    l=len(s)
    if s[0]=="i":
        que_r.appendleft(s[7:])
    elif s[6]==" ":
        try:
            que_r.remove(s[7:])
        except: pass
    elif l>10:
        que_r.popleft()
    elif l>6:
        que_r.pop()

print(*que_r)
### BUGGY CODE ###

N=int(input())
S = [input() for i in range(N)]
P=[]
A=[]
for i in range(len(S)):
    P.append(S.count(S[i]))

for k in range(len(P)):
    if P[k]==max(P):
        A.append(S[k])

A0=set(A)
A1=list(A0)
A1.sort()

for List in A1:
    print(List)

### FIXED CODE ###

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

P=collections.Counter(S)

y=max(P.values())
A = [k for k, v in P.items() if v == y]

A.sort()

for List in A:
    print(List)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()


### FIXED CODE ###

# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
s = input()
q = int(input())
for _ in range(q):
    qi = input()
    if len(qi) <= 2:
        s = s[::-1]
    else:
        _,F,C = qi.split()
        if F == "1":
            s = C + s
        else:
            s = s + C           
print(s)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

t = deque(S)
reverse = False
for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                t.append(C)
            else:
                t.appendleft(C)
        elif F == '2':
            if reverse:
                t.appendleft(C)
            else:
                t.append(C)
result = ''.join(t)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

import numpy as np
n = int(input())

l = np.int32(input().split())
l.sort()

c = np.bincount(l,minlength = 2100)

cum = c.cumsum()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += cum[min(l[i]+l[j]-1, 1000)] - (j+1)
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
l = sorted([int(i) for i in input().split()])

ans = 0
for i in range(n):
    for j in range(i+1,n):
        a = l[i]
        b = l[j]
        tri = bisect.bisect_left(l,a+b)
        ans += tri-j-1
        
print(ans)
### BUGGY CODE ###

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

for _ in range(m):
    maximum = a.index(max(a))
    a[maximum] = a[maximum] // 2

print(sum(a))


### FIXED CODE ###

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_minus = [-x for x in a]
heapify(a_minus)

pop = lambda: -heappop(a_minus)
push = lambda x: heappush(a_minus,-x)

for _ in range(m):
    x = pop()
    push(x//2)

print(-sum(a_minus))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
N = int(input())
a = list(map(int, input().split(" ")))
c = []
 
for i in a:
  count = 0
  while not(i % 2):
    a = int(i / 2)
    count += 1
    c.append(count)
print(min(c))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
N = int(input())
a = list(map(int, input().split(" ")))
c = []
 
for i in a:
  count = 0
  while not(i % 2):
    i = int(i / 2)
    count += 1
  c.append(count)
print(min(c))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [[]]
for i in range(N):
    As.append(list(map(int, input().split())))

Cs = [0] * (N + 1)
Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
while sw:
    c = 0
    wa = []
    e = N + 1
    f = N - 1
    for i in range(1, e):
        if Ks[i] or Cs[i] == f:
            continue
        if i > As[i][Cs[i]]:
            a = As[i][Cs[i]]
            b = i
        else:
            a = i
            b = As[i][Cs[i]]
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            Cs[a] = Cs[a] + 1
            Cs[b] = Cs[b] + 1
            tab.remove((a, b))
            wa.append(a)
            wa.append(b)
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in wa:
        Ks[i] = False
    d = d + 1
    if c == 0:
        print(-1)
        break

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))
### BUGGY CODE ###

n = int(input())

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

count = 1
for i in a:
    count *= i
if count > 10 ** 18:
    print(-1)
else:
    print(count)

### FIXED CODE ###

n = int(input())

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

count = 1
if 0 in a:
    print(0)
else:

    for i in a:
        count *= i
        if count > 10 ** 18:
            print(-1)
            break
    if count <= 10 ** 18:
        print(count)
### BUGGY CODE ###

n = int(input())
r = 0
for i in range(n):
    r += i
print(r)


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

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

for i in range(n):
    m=m*a[i]

if m > 10**18:
    print("-1")
else:
    print(m)



### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    m=1
    for i in a:
        m*=i
        if 10**18 < m:
            print(-1)
            break
    else:
        print(m)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

cnt = 0
for i in range(N-1):
    for j in range(i+1, N):
        if j-i == A[j]+A[i]:
            cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

L = dict(); R = dict()
for i in range(N):
    l = i + A[i]
    if l in L:
        L[l] += 1
    else:
        L[l] = 1
    r = i - A[i]
    if r in R:
        R[r] += 1
    else:
        R[r] = 1

ans = 0
for x in R:
    if x in L:
        ans += L[x] * R[x]

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

import itertools

n,y = map(int,input().split())
a = [1000,5000,10000]
l = list(itertools.product(a,repeat = n))

for i in range(len(l)):
    if sum(l[i]) == y:
        o = l[i].count(10000)
        p = l[i].count(5000)
        q = l[i].count(1000)
        print(o,p,q)
        exit(0)

print('-1 -1 -1')

### FIXED CODE ###

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

for i in range(0,n+1):
    for j in range(0,n+1-i):
        k = max(0,n-i-j)
        if 10000*i + 5000*j + 1000*k == y:
            print(i,j,k)
            exit(0)

print(-1,-1,-1)
### BUGGY CODE ###

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

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)
        return mx

    mx=0
    for key in range(N):
        mx=max(mx,dfs(key))

    return mx

print(main())


### FIXED CODE ###

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

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(N)]
    for i in range(M):
        x,y=list(map(int,sys.stdin.readline().split()))
        dic[x-1].append(y-1)


    dp=[0]*(N)
    def dfs(frm):
        if dp[frm]:
            return dp[frm]

        mx=0
        if not dic[frm]:
            return 0

        for val in dic[frm]:
            mx=max(mx,dfs(val)+1)

        dp[frm]=mx
        return mx

    mx=0
    for key in range(N):
        mx=max(mx,dfs(key))

    return mx

print(main())
### BUGGY CODE ###

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

p = [sum(p[0+i:k+i]) for i in range(n-k+1)]
print((max(p)+k)/2)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
a = sum(p[0:k])
l = [a]
for i in range(n-k):
    a = a-p[i]+p[i+k]
    l.append(a)
print((max(l)+k)/2)
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def join(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            #S[aj][0] = S[ai][0]
            S[aj] = S[ai]
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    N, M, K = iim()
    S = [[i] for i in range(N+1)]
    mk = set()
    for i in range(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk.add((ai, bi))
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk.add((ai, bi))

    ans = [0] * (N+1)
    #print(S)
    for i in range(1, N+1):
        aa = 0
        for j in range(i+1, N+1):
            if (i, j) in mk:
                continue
            if same(i, j):
                ans[i] += 1
                ans[j] += 1
    print(*ans[1:])



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        if x < 0:
            return i
        S[i] = find(x)
        return S[i]

    def join(i, j):
        ai = find(i)
        aj = find(j)
        diff = ai - aj
        #print("j", ai, aj)
        if diff == 0:
            return
        elif diff > 0:
            ai, aj = aj, ai
        S[ai] += S[aj]
        S[aj] = ai
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj
    def size(i):
        return -S[find(i)]

    N, M, K = iim()
    S = [-1] * N
    T = [1] * N
    for i in range(M):
        ai, bi = iim()
        ai -= 1; bi -= 1
        join(ai, bi)
        T[ai] += 1
        T[bi] += 1
        #print(ai, bi, S)

    U = [set() for i in range(N)]
    for i in range(K):
        ai, bi = iim()
        ai -= 1; bi -= 1
        U[ai].add(bi)
        U[bi].add(ai)
    #print(S)
    #print(T)

    ans = [size(i) - T[i] - sum(same(i, j) for j in U[i]) for i in range(N)]
    print(*ans)


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

import numpy as np
import copy

def main():
    l, r = map(int, input().split())
    
    ans_tmp = 2019
    for j in range(r-l):
        for k in range(r-l):
            ans = ((l+j)*(l+(k+1)))% 2019
            if ans < ans_tmp:
                ans_tmp = ans
                if ans == 0:
                    break
        
    print(ans_tmp)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np
import copy

def main():
    l, r = map(int, input().split())
    
    ans_tmp = 2019
    if r-l >= 2019:
        ans_tmp = 0
    else:
        for j in range(r-l):
            for k in range(j,r-l):
                ans = ((l+j)*(l+(k+1)))% 2019
                if ans == 0:
                    ans_tmp = 0
                    break
                elif ans < ans_tmp:
                    ans_tmp = ans
                
        
    print(ans_tmp)

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

#####コピペ
def BellmanFord(edges, num_v, source):
    # グラフの初期化
    inf = float("inf")
    dist = [-inf for i in range(num_v)]
    dist[source - 1] = 0

    # 辺の緩和
    buf = 0
    for i in range(num_v * 2):
        for edge in edges:
            if dist[edge[1] - 1] < dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i >= num_v:
                    dist[edge[1] - 1] = inf
        if i == num_v - 1:
            buf = dist[-1]
    if dist[-1] != buf or dist[-1] == -inf:
        return -1
    return max(dist[-1], 0)
##########################################################################
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N, M, P = LI()
cou = int(0)
maxC = 10000
d = [[float("inf") for i in range(N)] for i in range(N)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
V = []*M
for i in range(M):
    a, b, c = list(map(int,input().split()))
    V.append((a,b,c-P))
print(BellmanFord(V, N, 1))


#print(ans)



### FIXED CODE ###

#####コピペ
def BellmanFord(edges, num_v, source):
    # グラフの初期化
    inf = float("inf")
    dist = [-inf for i in range(num_v)]
    dist[source - 1] = 0

    # 辺の緩和
    buf = 0
    for i in range(num_v * 2):
        for edge in edges:
            if dist[edge[1] - 1] < dist[edge[0] - 1] + edge[2]:
                dist[edge[1] - 1] = dist[edge[0] - 1] + edge[2]
                if i >= num_v:
                    dist[edge[1] - 1] = inf
        if i == num_v - 1:
            buf = dist[-1]
    if dist[-1] != buf or dist[-1] == -inf:
        return -1
    return max(dist[-1], 0)
##########################################################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N, M, P = LI()
cou = int(0)
maxC = 10000
d = [[float("inf") for i in range(N)] for i in range(N)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
V = []*M
for i in range(M):
    a, b, c = list(map(int,input().split()))
    V.append((a,b,c-P))
print(BellmanFord(V, N, 1))

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

n = int(input())
data_list = []
for i in range(n):
    data_list.append(input(""))

data_list_a = set(data_list)
data_list_a = list(data_list_a)

data_a = [0 for i in range(len(data_list_a))]

for i in range(len(data_list_a)):
    for j in range(n):
        if data_list[j] == data_list_a[i]:
            data_a[i] += 1


#print(data_list)
#print(data_list_a)
#print(data_a)
ans_a = []
d = max(data_a)
for i in range(len(data_list_a)):
    if data_a[i] == d:
        ans_a.append(i)

ans = []

for i in range(len(ans_a)):
    ans.append(data_list_a[ans_a[i]])

ans.sort()

for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

n = int(input())
data_list = []
for _ in range(n):
    data_list.append(input(""))

data_list_a = set(data_list)
data_list_a = list(data_list_a)
m = len(data_list_a)

data_a = [0 for _ in range(m)]

data_dic = dict(zip(data_list_a, data_a))

for i in range(n):
    data_dic[data_list[i]] += 1

data_score = data_dic.values()
max_value = max(data_score)
ans = []


for i in range(m):
    if data_dic[data_list_a[i]] == max_value:
        ans.append(data_list_a[i])


ans.sort()

for i in range(len(ans)):
    print(ans[i])