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

mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, m = map(int,raw_input().split())
    
    adj_list = [[] for _ in range(n+5)]
    
    q = []
    
    ans = [-1] * (n+5)
    
    failed = False
    
    for _ in range(m):
        a, b = map(int,raw_input().split())    
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    q.append(1)
    
    #print(adj_list)
    
    visited = set()
    
    visited.add(1)
    
    while len(q):
        sz = len(q)
        for _ in range(sz):
            cur = q.pop(0)
            for nei in adj_list[cur]:
                if nei not in visited:
                    ans[nei] = cur
                    q.append(nei)
                    visited.add(nei)
    
    
    print('Yes')
    for i in range(2, n+1):
        print(ans[i])
            
            
        
        
    
    

main()

### FIXED CODE ###

from collections import deque

mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n, m = map(int,raw_input().split())
    
    adj_list = [[] for _ in range(n+5)]
    
    q = deque()
    
    ans = [-1] * (n+5)
    
    failed = False
    
    for _ in range(m):
        a, b = map(int,raw_input().split())    
        adj_list[a].append(b)
        adj_list[b].append(a)
    
    q.append(1)
    
    #print(adj_list)
    
    visited = set()
    
    visited.add(1)
    
    while len(q):
        sz = len(q)
        for _ in range(sz):
            cur = q.popleft()
            for nei in adj_list[cur]:
                if nei not in visited:
                    ans[nei] = cur
                    q.append(nei)
                    visited.add(nei)
    
    
    print('Yes')
    for i in range(2, n+1):
        print(ans[i])
            
            
        
        
    
    

main()
### BUGGY CODE ###

def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for i in range(n + 1)] for j in range(n + 1)]

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sm_mx + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break

        ans += dp[n][i][i*a]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, a = map(int, input().split())
    x = tuple(map(int, input().split()))

    sm_mx = sum(x)

    dp = [[[0] * (sm_mx + 1) for _ in range(n + 1)] for _ in range(n + 1)]

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

    for i, e in enumerate(x, 1):
        for j in range(n + 1):
            for sm in range(sum(x[:i]) + 1):
                if sm < e:
                    dp[i][j][sm] = dp[i-1][j][sm]
                elif j >= 1 and sm >= e:
                    dp[i][j][sm] = dp[i-1][j][sm] + dp[i-1][j-1][sm-e]

    ans = 0
    for i in range(1, n + 1):
        if i > sm_mx / a:
            break
        ans += dp[n][i][i*a]

    print(ans)


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

N=int(input())
X=list(map(int,input().split()))
for i in range(N):
    print(sorted(X[0:i]+X[i+1:N])[(N-1)//2])

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
X_s=sorted(X)
ans1=X_s[N//2]
ans2=X_s[N//2-1]
for i in X:
    print(ans1*(i<=ans2) or ans2)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc034/tasks/agc034_b

S = input()
count = 0
while "ABC" in S:
    # print(S)
    count += S.count("ABC")
    S = S.replace("ABC", "BCA")
print(count)

### FIXED CODE ###

# 解説
# ABC -> CBA
# BCは増えない&離れない
# AD -> DAを考える
# Aの右にBCが何個あるか

s = input()
n = len(s)
i = 0
ans = 0
count_a = 0

while i < n:
    if s[i] == 'A':
        count_a += 1
    elif i < n - 1 and s[i:i+2] == 'BC' and count_a > 0:
        ans += count_a
        i += 1
    else:
        count_a = 0
    i += 1
print(ans)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        #z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        res1, res2 = [0], [0]
        c1 = c2 = 0
        for i in range(H-j):
            ij = i+j
            if C1[i] == C2[ij]:
                c1 += 1
            res1.append(c1)
            if C1[ij] == C2[i]:
                c2 += 1
            res2.append(c2)
        res1.reverse();  Z1.append(res1)
        res2.reverse();  Z2.append(res2)

    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
# print(N)
# print(A)
A.sort(reverse=True)
ans = 0
N -= 2
ans += A[0]
A.pop(0)
# print("test" + str(ans))
if N == 0:
    print(ans)
    exit()

while N > 0:
    if N == 0:
        print(ans)
        exit()
    elif N == 1:
        ans += A[0]
        print(ans)
        exit()
    elif N >= 2:
        ans += 2 * A[0]
        N -= 2
        A.pop(0)
        if N == 0:
            print(ans)
            exit()


### FIXED CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: x * (-1), A))

heapq.heapify(A)

ans = 0
N -= 2
ans += heapq.heappop(A) * (-1)

if N == 0:
    print(ans)
    exit()
elif N == 1:
    ans += A[0]
    print(ans)
    exit()
elif N >= 2:
    q = N // 2
    r = N % 2
    for i in range(1, q + 1):
        ans += 2 * heapq.heappop(A) * (-1)
    if r == 1:
        ans += heapq.heappop(A) * (-1)
    print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
ans=[]
n=len(s)
for i in range(n):
    for j in range(n):
        ans.append(s[i:j+1])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
if n==1:
    print(s)
else:
    print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
ans=[]
for i in range(n):
    for j in range(i+1,i+k+1):
        ans.append(s[i:j])
ans=list(set(ans))
ans.sort()
if "" in ans:
    ans.pop(0)
print(ans[k-1])
### BUGGY CODE ###

p=int(input())
A=list(map(int,input().split()))

B=[0]*p
mod=p

FACT=[1]
for i in range(1,p):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(p-1,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0


for i in range(p):
    if A[i]==0:
        continue

    B[0]+=1
    for j in range(p):
        B[j]+=(-Combi(p-1,j)*pow(-i,p-1-j,p))%p

print(*[b%p for b in B])

    
    




### FIXED CODE ###

p=int(input())
A=list(map(int,input().split()))

B=[0]*p

INV=[None]*p# 1/aのリストを予め作っておく.
for i in range(1,p):
    INV[i]=pow(i,p-2,p)

Combi=[None]*p# Combi[i]=nCi を表す
Combi[0]=1
for i in range(1,p):
    Combi[i]=Combi[i-1]*(p-i)*INV[i] %p


for i in range(p):
    if A[i]==0:
        continue

    B[0]+=1
    POW=1
    for j in range(p):
        B[p-1-j]=(B[p-1-j]-Combi[j]*POW)%p
        POW=POW*(-i)%p

print(*[b%p for b in B])
### BUGGY CODE ###

n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            u=(u-1)//n
        else:
            v=(v-1)//n
    print(u+1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)
### BUGGY CODE ###

import sys
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))

dp = [sys.maxsize for i in range(n)]
dp[0] = 0
for i in range(n):
	for j in range(i+1,i+k+1):
		if j<n:
			dp[j] = min(dp[j],dp[i]+abs(arr[i]-arr[j]))
print(dp[-1])

### FIXED CODE ###

import sys
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))

dp = [sys.maxsize for i in range(n)]
dp[0] = 0
for i in range(n):
	for j in range(i+1,i+k+1):
		if j<n:
			dp[j] = min(dp[j],dp[i]+abs(arr[i]-arr[j]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split(" ")))
def bubble(A, N):
    count = 0
    flag = True
    while flag == True:
        for j in range(N-1, 0, -1):
            flag = False
            if A[j] < A[j - 1]:
                A[j -1],A[j] = A[j], A[j - 1]
                count += 1
                flag = True
        print(" ".join(map(str, A)))
        print(count)

bubble(A, N)
    

### FIXED CODE ###

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


def bubble_sort(A, N):
    cnt = 0
    flag = True
    while(flag):
        flag = False
        for i in range(N-1, 0, -1):
            if(A[i-1] > A[i]):
                A[i-1], A[i] = A[i], A[i-1]
                cnt += 1
                flag = True

    print(" ".join(list(map(str, A))))
    print(cnt)

bubble_sort(A, N)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: List[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H

    for item in codList:
        columnSumList[item[1] - 1] += 1
        rowSumList[item[0] - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row + 1, column + 1) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

K, S = map(int,input().split())

l1 = [i for i in range(K+1)]
r = 0
for i in l1:
  for j in l1:
    if S - i - j in l1:
      r += 1
print(r)

### FIXED CODE ###

K, S = map(int,input().split())
 
l1 = tuple([i for i in range(K+1)])
r = 0
for i in l1:
  if i > S:
    continue
  else:
    for j in l1:
      if i + j > S:
        continue
      elif S - i - j <= K:        
        r += 1
print(r)
### BUGGY CODE ###

import math


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

def main():

	max = 0
	for i in range(li[2]+1):
		l = (math.floor((li[0]*i)/li[1]) - li[0]*(math.floor(i/li[1])))
		if l > max:
			max = l
	return(print(max))

      

main()

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
x = 0
if N < B:
    x = N
else:
    x = B - 1
 
print(math.floor(A * x / B) - A * math.floor(x / B))
### BUGGY CODE ###

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

#import time
#start = time.time()

MOD = 1000000007
numbers = S[:]
numbers.sort()
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

for x in range(X+1):
    dp[0][x] = x

for i in range(N):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % numbers[i]]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)
#elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

### FIXED CODE ###

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

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 'YES'
for i in range(n-1):
   for j in range(i+1, n):
      if a[i] == a[j]:
         ans = 'NO'
         break
print(ans)

### FIXED CODE ###

n = int(input())
a_bef = list(map(int, input().split()))
ans = 'YES'
a_aft = sorted(a_bef)
for i in range(n-1):
   if a_aft[i] == a_aft[i+1]:
      ans = 'NO'
      break
print(ans)
### BUGGY CODE ###

from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
for i in range(R):
  r[i] -= 1
g = [[10 ** 8] * N for i in range(N)]
for i in range(M):
  A,B,C = map(int,input().split())
  A -= 1 
  B -= 1
  g[A][B] = C
  g[B][A] = C
def warchall_floyd(n):
  for i in range(n):
    #経由する頂点
    for j in range(n):
      #始点
      for k in range(n):
        #終点
        g[j][k] = min(g[j][k],g[j][i]+g[i][k])
        
warchall_floyd(N)
ans = float('inf')
for i in permutations(r):
  now = 0
  for j in range(R-1):
    now += g[i[j]][i[j+1]]
  if now < ans:
    ans = now
print(ans)

### FIXED CODE ###

from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))
for i in range(R):
  r[i] -= 1
g = [[10 ** 8] * N for i in range(N)]
for i in range(M):
  A,B,C = map(int,input().split())
  A -= 1 
  B -= 1
  g[A][B] = C
  g[B][A] = C
def warchall_floyd(n):
  for i in range(n):
    #経由する頂点
    for j in range(n):
      #始点
      for k in range(n):
        #終点
        g[j][k] = min(g[j][k],g[j][i]+g[i][k])
        
warchall_floyd(N)
ans = float('inf')
for i in permutations(r):
  now = 0
  for j in range(R-1):
    now += g[i[j]][i[j+1]]
  if now < ans:
    ans = now
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])
### BUGGY CODE ###

while 1:
    n=int(input())
    if n==0:break
    a=0
    for i in range(1,n//2):a+=(n+2*i-1)//(2*i)-1
    print(8*(2*n-1+a))

### FIXED CODE ###

while 1:
    n=int(input())
    if n==0:break
    a=0;i=1;b=n//2
    while i*i<b:a+=((b-1)//i+1)-i-1;i+=1
    a=(a+b-1)*2+i
    print(8*(a+n))
### BUGGY CODE ###

from bisect import bisect_right
s, t = open(0).read().split()
S, T = set(s), set(t)
if T & S != T:
    print(-1)
    quit()
d, l = dict(), dict()
for idx, c in enumerate(s):
    d[c] = d.get(c, []) + [idx]
    l[c] = l.get(c, 0) + 1
prev = -1
loop = 0
for c in t:
    idx = bisect_right(d[c], prev)
    if idx >= l[c]:
        loop += 1
        prev = d[c][0]
    else:
        prev = d[c][idx]
print((loop) * len(s) + prev + 1)

### FIXED CODE ###

from bisect import bisect_right
s = tuple(map(lambda c: ord(c) - ord("a"), input()))
t = tuple(map(lambda c: ord(c) - ord("a"), input()))
S, T = set(s), set(t)
if T & S != T:
    print(-1)
    quit()
d, l = [[] for _ in range(26)], [0] * 26
for idx, c in enumerate(s):
    d[c].append(idx)
    l[c] += 1
prev = -1
loop = 0
for c in t:
    idx = bisect_right(d[c], prev)
    if idx >= l[c]:
        loop += 1
        prev = d[c][0]
    else:
        prev = d[c][idx]
print((loop) * len(s) + prev + 1)
### BUGGY CODE ###

h,w=map(int,input().split())
s=[input() for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
for i in range(h):
  if s[i][0]=='.':
    l[i][0]=1
  if s[i][w-1]=='.':
    r[i][w-1]=1
for i in range(w):
  if s[0][i]=='.':
    u[0][i]=1
  if s[h-1][i]=='.':
    d[h-1][i]=1
for i in range(h):
  for j in range(w):
    if j>=1:
      if s[i][j]=='.':
        l[i][j]=l[i][j-1]+1
    if j<w-1:
      if s[i][w-j-2]=='.':
        r[i][w-j-2]=r[i][w-j-1]+1
    if i>=1:
      if s[i][j]=='.':
        u[i][j]=u[i-1][j]+1
    if i<h-1:
      if s[h-i-2][j]=='.':
        d[h-i-2][j]=d[h-i-1][j]+1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
s=[input() for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
for i in range(h):
  if s[i][0]=='.':
    l[i][0]=1
  if s[i][w-1]=='.':
    r[i][w-1]=1
for i in range(w):
  if s[0][i]=='.':
    u[0][i]=1
  if s[h-1][i]=='.':
    d[h-1][i]=1
for i in range(h):
  for j in range(w):
    if j>=1:
      if s[i][j]=='.':
        l[i][j]=l[i][j-1]+1
    if j<w-1:
      if s[i][w-j-2]=='.':
        r[i][w-j-2]=r[i][w-j-1]+1
    if i>=1:
      if s[i][j]=='.':
        u[i][j]=u[i-1][j]+1
    if i<h-1:
      if s[h-i-2][j]=='.':
        d[h-i-2][j]=d[h-i-1][j]+1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
p1 = 1
for i in range(k):
	p1 *= l[i]
for i in range(k,n):
	p2 = p1
	p2 *= l[i]
	p2 //= l[i-k]
	#print(p1,p2)
	print('Yes' if p2 > p1 else 'No')
	p1 = p2

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
p1 = 0
for i in range(k):
	p1 += l[i]
for i in range(k,n):
	p2 = p1
	p2 += l[i]
	p2 -= l[i-k]
	#print(p1,p2)
	print('Yes' if p2 > p1 else 'No')
	p1 = p2
### BUGGY CODE ###

def factorize(n):
    p = n
    while True:
        if p % 2 == 0:
            p //= 2
            yield 2
        else:
            break

    for i in range(3,n+1,2):
        while True:
            if p % i == 0:
                p //= i
                yield i
            else:
                break

n = int(input())
l = factorize(n)

print(str(n)+":",*list(l))

### FIXED CODE ###

import math

def factorize(p):
    l = []
    while p % 2 == 0:
        p //= 2
        l.append(2)

    r = 3
    while r < int(math.sqrt(p)+1):
        if p % r == 0:
            p //= r
            l.append(r)
        else:
            r += 2

    if p != 1:
        l.append(p)

    return l

n = int(input())
l = factorize(n)

print(str(n)+":",*l)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0 for i in range(N)]
for i in range(1,N):
  s = 10**10
  for j in range(1,min(i,K)+1):
    s = min(s,dp[i-j]+abs(h[i]-h[i-j]))
  dp[i] = s
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]
for i in range(1,N):
    a = DP[i-1] + abs(H[i]-H[i-1])
    for j in range(2,min(K,i)+1):
        b = DP[i-j] + abs(H[i]-H[i-j])
        a = min(a,b)
    DP.append(a)
print(DP[N-1])
### BUGGY CODE ###

from collections import Counter
n=int(input())
S=[]
for _ in range(n):
    S.append(input())
    
cnt=Counter(S)
list=[]
for k in cnt.most_common():
    if k[1] != cnt.most_common()[0][1]:
        break
    list.append(k[0])
list.sort()

for i in list:
    print(i)

### FIXED CODE ###

from collections import Counter
import sys
n=int(sys.stdin.readline().rstrip())
S=[sys.stdin.readline().rstrip() for _ in range(n)]
    
cnt=Counter(S)
ma = max(cnt.values())
list=[]
for k in cnt.keys():
    if cnt[k] == ma:
      list.append(k)

list.sort()
for i in list:
    print(i)