Harryxun/stf_run huggingface dataset:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    if A[0] == A[1]:
        B[A[i]] = 2
    else:
        B[A[i]] = 1
    for i in range(1, N - 1):
        if A[i-1] == A[i] or A[i+1] == A[i]:
            B[A[i]] = 2
        else:
            B[A[i]] = 1
    if A[-2] == A[-1]:
        B[A[i]] = 2
    else:
        B[A[i]] = 1
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()


### FIXED CODE ###

#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    for i in range(0, N):
        if i == 0:
            if A[i + 1] == A[i]:
                B[A[i]] = 2
                continue
        elif i == N - 1:
            if A[i - 1] == A[i]:
                B[A[i]] = 2
                continue
        elif A[i - 1] == A[i] or A[i + 1] == A[i]:
            B[A[i]] = 2
            continue
        B[A[i]] = 1
    # print(*B.items())
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
                # print(b * i)
    res = 0
    for v in B.values():
        if v:
            res += 1
    # print(*B.items())
    print(res)
    return

main()
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,K=rl()

td_1 = [0]*N
td_rem = []
for _ in range(N):
    t,d = rl()
    t -= 1
    if td_1[t] == 0:
        td_1[t] = d
    else:
        if d <= td_1[t]:
            td_rem += [d]
        else:
            td_rem += [td_1[t]]
            td_1[t] = d


td_1.sort(reverse=True)
td_rem.sort(reverse=True)
#print(td_1)
#print(td_rem)
import numpy as np
td_1 = list(np.cumsum([0] + td_1[:td_1.index(0)]))
td_rem = list(np.cumsum([0]+td_rem))

ans = [0 for _ in range(K+1)]
sum_l = 0
for i in range(1,K+1):
    if len(td_1)-1 >= i and len(td_rem)-1>=K-i:
        ans[i] = i*i + td_1[i] + td_rem[K-i]

#print(td_1)
#print(td_rem)
#print(ans)
print(max(ans))


### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,K=rl()
td = [rl() for _ in range(N)]

from operator import itemgetter
key0 = itemgetter(0)
key1 = itemgetter(1)
td.sort(key=key1,reverse=True)

netas = set()
dup = []

for t,d in td[:K]:
    if t in netas:
        dup.append(d)
    else:
        netas.add(t)

score = len(netas)**2 + sum(map(key1,td[:K]))
ans = score
for t,d in td[K:]:
    if t not in netas and dup != []:
        netas.add(t)
        dup_ = dup.pop(-1)
        score += 2*len(netas)-1 + d - dup_
        ans = max(ans,score)
print(ans)
n, x = map(int,input().split())

if x > n // 2:
    x = n - x

xx = x
yy = n - x

ans = n
i = 0

while True:
    ans += 2 * (yy // xx) * xx
    yy %= xx

    if yy == 0:
        ans -= xx
        break

    if yy < xx:
        tmp = xx
        xx = yy
        yy = tmp

print(ans)


### FIXED CODE ###

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

l.sort()
ans = 0

for i in range(n):
    ans += l[2 * i]

print(ans)
N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        par[a]=b
        siz[b]+=siz[a]

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for _ in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)

### FIXED CODE ###

N,M,K=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for _ in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)
i = int(raw_input())

while (i):
	i -= 1
	st = []
	n = raw_input()

	for s in n:
		st.append(s)

	s.sort()
	a = int("".join())
	b = int("".join(s[::-1]))

	print b - a

### FIXED CODE ###

i = int(raw_input())

while (i):
	i -= 1
	st = []
	n = raw_input()

	for s in n:
		st.append(s)

	st.sort()
	a = int("".join(st))
	b = int("".join(st[::-1]))

	print b - a
n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(111)] for j in range(100111)]

for i in range(0,n):
    for sum_w in range(0,w+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
weight=[]
value=[]
for i in range(n):
    q,r=map(int,input().split())
    weight.append(q)
    value.append(r)

dp=[[0 for i in range(100111)] for j in range(111)]

for i in range(0,n):
    for sum_w in range(0,w+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w]=max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])
        dp[i+1][sum_w]=max(dp[i][sum_w],dp[i+1][sum_w])

print(dp[n][w])
s = input()
num = len(s)
ans = 0

def count(pos, befor, co):
  global ans
  if pos >= num:
    if ans < co:
      ans = co
    return True
  
  for p in range(1, num-pos+1):
    if ans > co + len(s[pos+p:]) + 1:
      break
    if s[pos:pos+p] != befor:
      a = count(pos + p, s[pos:pos+p], co+1)
        

  return True

ans = 0

a = count(0, "", 0)
print(ans)


### FIXED CODE ###

s = input()
num = len(s)
ans = 0
pos = 0
 
while True:
  c = s[pos]
  count = 0
  for i in range(num - pos):
    if s[pos + i] == c:
      count += 1
    else:
      ans += (count//3)*2  
      if i < num:
        if count % 3 == 1:
          ans += 1
        elif count % 3 == 2:
          ans += 2
          pos += 1
          pos += count
          count = 0
          
      break
  pos += count
  
  if pos >= num:
    ans += (count // 3) * 2 
    if count % 3 != 0:
      ans += 1
 
    break
 
 
print(ans)
import sys

#run by python3                                                                            

class Node:
    def __init__(self, key):
	self.key = key
        self.right = None
	self.left = None

def insert(T, z): #z is node which you would like to insert                                
        #initialization                                                                    
    y = None #parent of x                                                                  
    x = T

	#search                                                                            
    while(x!=None):
        y = x
        if(z.key < x.key):
            x = x.left
        else:
            x = x.right

	#insert                                                                            
    if(y==None):
        T = z
    elif(z.key < y.key):
	y.left = z
    else:
        y.right = z

    return T

def inorder_walk(node):
    if node.left:
	inorder_walk(node.left)
    print ('', node.key, end='')
    if node.right:
	inorder_walk(node.right)


def preorder_walk(node):
    print ('', node.key,end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
	preorder_walk(node.right)


T = None
num = int(sys.stdin.readline())

for _ in range(num):
    cmd = sys.stdin.readline()
    if(cmd.startswith('i')):
	n = Node(int(cmd[7:]))
	T = insert(T, n)
    else:
        inorder_walk(T)
	print()
	preorder_walk(T)
	print()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
 
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
 
 
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
 
 
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
 
 
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
 
 
n = int(stdin.readline())
 
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

def lcm(x,y):
    return x*y//gcd(x,y)

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
na = [i*0.5 for i in a]
l = 1
for i in range(n):
    l = lcm(l,na[i])

l2 = l*2
if l-1 > m:
    ans = 0
else:
    ans = (m-(l-1))//l2 + 1
        
print(ans)

### FIXED CODE ###

def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

def lcm(x,y): return x*y//gcd(x,y)

def f(x):
    cnt = 0
    while(x%2==0):
        x //= 2
        cnt += 1
    return cnt

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
na = [i//2 for i in a]

t = f(na[0])
for i in range(1,n):
    if t != f(na[i]):
        print(0)
        exit()

l = na[0]
for i in range(1,n): l = lcm(l,na[i])

if m < l:
    ans = 0
else:
    ans = 1 + (m-l)//(2*l)

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

a.sort()
A = [0] * 100000
for i in a:
  A[i] += 1

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

for n in range(q):
  b,c = list(map(int, input().split()))
  ans += (c * A[b]) - (b * A[b])
  A[c] += A[b]
  A[b] = 0
  print(ans)
 


### FIXED CODE ###

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

A = [0] * 100001
for i in a:
  A[i] += 1

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

for n in range(q):
  b,c = list(map(int, input().split()))
  ans += (c * A[b]) - (b * A[b])
  A[c] += A[b]
  A[b] = 0
  print(ans)
A,B = list(map(int,input().split(" ")))
S = input()

for i in range(len(S)):
    if i==A:
        if S[i]!="-":
            print("No")
            exit()
    else:
        if not ord('0')<=ord(str(i))<=ord('9'):
            print("No")
            exit()
print("Yes")
            


### FIXED CODE ###

A,B = list(map(int,input().split(" ")))
S = input()

for i in range(len(S)):

    if i==A:
        if S[i]!="-":
            print("No")
            exit()
    else:
        if not ord('0')<=ord(str(S[i]))<=ord('9'):
            print("No")
            exit()
print("Yes")
S = [input() for _ in range(int(input()))]
T = [input() for _ in range(int(input()))]
ans = 0
for s in set(S):
    score = S.count(s) - T.count(s)
    if score > ans:
        ans = score
print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
print('Yes' if a+b>=c else 'No')
[X,Y,A,B,C] = [int(x) for x in input().split()]
R_list = [int(x) for x in input().split()]
G_list = [int(x) for x in input().split()]
T_list = [int(x) for x in input().split()]
R_list.sort()
G_list.sort()
T_list.sort()
total = 0
ans = 0
r = 0
g = 0
for i in range(X+Y):
    if r == X:
        R_list = [-1]
    if g == Y:
        G_list = [-1]
    if max(R_list[-1],G_list[-1],T_list[-1]) == R_list[-1]:
        ans += R_list.pop(-1)
        r += 1
    elif max(R_list[-1],G_list[-1],T_list[-1]) == G_list[-1]:
        ans += G_list.pop(-1)
        g += 1
    elif max(R_list[-1],G_list[-1],T_list[-1]) == T_list[-1]:
        ans += T_list.pop(-1)
print(ans)

### FIXED CODE ###

[X,Y,A,B,C] = [int(x) for x in input().split()]
R_list = [int(x) for x in input().split()]
G_list = [int(x) for x in input().split()]
T_list = [int(x) for x in input().split()]
R_list.sort()
G_list.sort()
T_list.sort()
ans = 0
r = 0
g = 0
for i in range(X+Y):
    if r == X:
        R_list = [0]
    if g == Y:
        G_list = [0]
    if len(T_list) == 0:
        T_list = [0]
    if max(R_list[-1],G_list[-1],T_list[-1]) == R_list[-1]:
        ans += R_list.pop(-1)
        r += 1
    elif max(R_list[-1],G_list[-1],T_list[-1]) == G_list[-1]:
        ans += G_list.pop(-1)
        g += 1
    elif max(R_list[-1],G_list[-1],T_list[-1]) == T_list[-1]:
        ans += T_list.pop(-1)
print(ans)
# 
# VScodeで入力をテキストから読み込んで標準入力に渡す
import sys
import os
f=open(r'.\D\D_input.txt', 'r', encoding="utf-8")
# inputをフルパスで指定
# win10でファイルを作るとs-jisで保存されるため、読み込みをutf-8へエンコードする必要あり
# VScodeでinput file開くとutf8になってるんだけど中身は結局s-jisになっているらしい
sys.stdin=f

#
# 入力スニペット
# num = int(input())
# num_list = [int(item) for item in input().split()]
# num_list = [input() for _ in range(3)]
##################################
# 
# 以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1, 2]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(3, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
len(prime_devisor_list)


### FIXED CODE ###

# start 21:14
a, b = [int(item) for item in input().split()]

# 素因数リスト
import math
def factor(num):
    divisor_list = [1]
    divisor = 2
    max_prime = int(math.sqrt(num))
    while max_prime >= divisor:
        if num % divisor == 0:
            divisor_list.append(divisor)
            num //= divisor

        else:
            divisor += 1
    divisor_list.append(num)
    return divisor_list

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

cd_list = set(factor(gcd(a, b)))

print(len(cd_list))
H, W, M = map(int, input().split())

B = [list(map(int, input().split())) for _ in range(M)]

bombs_row = [0] * H
bombs_col = [0] * W

for b in B:
    bombs_row[b[0] - 1] += 1
    bombs_col[b[1] - 1] += 1

row_max = max(bombs_row)
col_max = max(bombs_col)

row_max_count = bombs_row.count(row_max)
col_max_count = bombs_col.count(col_max)

ans = row_max + col_max

possible_point = row_max_count * col_max_count

bombed_point = 0

for b in B:
    if bombs_row[b[0]] == row_max and bombs_col[b[1]] == col_max:
        bombed_point += 1

if bombed_point == possible_point:
    ans -= 1

print(ans)


### FIXED CODE ###

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

B = [list(map(int, input().split())) for _ in range(M)]

bombs_row = [0] * H
bombs_col = [0] * W

for b in B:
    bombs_row[b[0] - 1] += 1
    bombs_col[b[1] - 1] += 1

row_max = max(bombs_row)
col_max = max(bombs_col)

row_max_count = bombs_row.count(row_max)
col_max_count = bombs_col.count(col_max)

ans = row_max + col_max

possible_point = row_max_count * col_max_count

bombed_point = 0

for b in B:
    if bombs_row[b[0] - 1] == row_max and bombs_col[b[1] - 1] == col_max:
        bombed_point += 1

if bombed_point == possible_point:
    ans -= 1

print(ans)
# -*- coding: utf-8 -*-

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

ans_list = []

for i in range(int(b / 2), n + 1):
  #print(int((a * i) / b), a * int(i / b), int((a * i) / b) - a * int(i / b))
  ans = int((a * i) / b) - a * int(i / b)
  ans_list.append(ans)
print(max(ans_list))



### FIXED CODE ###

# -*- coding: utf-8 -*-
# x = p * b + q
# 0 <= q < b
# int(a * p + a * q / b) - a * int(p - q / b)
# = a * p + int(a * q / b) - a * p
# = int(a * q / b)

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

print(a * min(b - 1, n) //  b)
# encoding: utf-8

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

ac_bc = n - x
s = ac_bc / 3
l = ac_bc - s
print ac_bc + s * 3 + l * 3

### FIXED CODE ###

# encoding: utf-8

n = int(raw_input())
l = map(int, raw_input().split())
l.sort()
print sum(l[::2])
print('Yes' if !input().replace('hi','') else 'No')

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = str(input())

print("Yes" if len(S.replace("hi", "")) == 0 else "No")
n = int(input())
A = list(map(int, input().split()))
num = 1
ans = 0
for i in range(n):
  if A[i] == num:
    num += 1
    ans += 1
if ans = 0:
  print("-1")
else:
print(n-ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
num = 1
ans = 0
for i in range(n):
  if A[i] == num:
    num += 1
    ans += 1
if ans == 0:
  print("-1")
else:
  print(n-ans)
input = input()
a, b, c = int(input[0]), int(input[1]), int(input[2])
k = int(input[3])
totalnum = 0
#a→b→cの順番で取ればいい。
for aa in range(k):
  if a != 0:
    a-=1
    totalnum+=1
  elif b != 0:
    b-=1
  elif c != 0:
    c-=1
    totalnum-=1
  else:
    break
print(totalnum)

### FIXED CODE ###

input = input().split(" ")
a, b, c = int(input[0]), int(input[1]), int(input[2])
k = int(input[3])
totalnum = 0
for nuum in range(4):
    if a>=k: #もしaの枚数がkを上回っていたら
        totalnum+=k
        k=0
        break
    elif a<k and a!=0: #もしaの枚数がkを下回っていたら
        totalnum+=a #totalnumをa分足して
        k-=a #kからaの枚数分引く
        a=0
    elif b>=k: #もしbの枚数がkを上回っていたら
        k=0
        break
    elif b<k and b!=0: #もしbの枚数がkを下回っていたら
        k-=b #bの枚数分だけkから引く。
        b=0
    elif c>=k: #もしcのところまで来たら
        totalnum-=k
        break
print(totalnum)
from math import gcd

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

p = [a[0]]
for i in range(1, n):
    p.append(gcd(p[i - 1], a[i]))

q = [a[-1]]
for i in range(n - 1):
    q.append(gcd(q[i], a[n - 2 - i]))
q = q[::-1]

res = 1
for i in range(n):
    if i - 1 < 0:
        res = max(res, q[i + 1])
    elif i + 1 >= n:
        res = max(res, p[i - 1])
    else:
        res = max(res, gcd(p[i - 1], q[i + 1]))

print(res)


### FIXED CODE ###

from fractions import gcd

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

p = [a[0]]
for i in range(1, n):
    p.append(gcd(p[i - 1], a[i]))

q = [a[-1]]
for i in range(n - 1):
    q.append(gcd(q[i], a[n - 2 - i]))
q = q[::-1]

res = 1
for i in range(n):
    if i - 1 < 0:
        res = max(res, q[i + 1])
    elif i + 1 >= n:
        res = max(res, p[i - 1])
    else:
        res = max(res, gcd(p[i - 1], q[i + 1]))

print(res)
N=int(input())
a=[]
for i in N:
  a.append=input()
print(len(collections.Counter(a)))

### FIXED CODE ###

import collections
N=int(input())
a=[]
for i in range(N):
  a.append(input())
print(len(collections.Counter(a)))
a=input()
b=int(input())
i=0
t=0
while t<0:
    if a[i]!='1':
        t=1
    else:
        i+=1
if i<(b-1):
    print(a[i])
else:
    print('1')


### FIXED CODE ###

a,b=map(int,input().split())
print((a-1)*(b-1))
from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())

S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

### FIXED CODE ###

import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])
n, m, c = map(int, input().split())
b = input().split()
a = [input().split() for input() in range(n)]

cnt = 0
for an in a:
    dot = 0
    for i, j in zip(an, b):
        dot += i*j
    dot += c
    cnt += (dot>0).astype(int)
    
print(cnt)

### FIXED CODE ###

n, m, c = map(int, input().split())
b = [int(x) for x in input().split()]
a = []
for i in range(n):
    a.append([int(x) for x in input().split()])
cnt = 0
for an in a:
    dot = 0
    for i, j in zip(an, b):
        dot += i*j
    dot += c
    cnt += int(dot>0)
    
print(cnt)
N = int(input())
hashmap = {}
Array = [[] for _ in range(N+1)]
for _ range(N):
  st = input()
  if st not in hashmap:
    hashmap[st] = 0
  hashmap[st]+=1
max_num = max(hashmap.values())
hashmap.sort()
for k,v in hashmap.items():
  if v == max_num:
    print(k)

### FIXED CODE ###

N = int(input())
hashmap = {}
Array = [[] for _ in range(N+1)]
for _ in range(N):
  st = input()
  if st not in hashmap:
    hashmap[st] = 0
  hashmap[st]+=1
max_num = max(hashmap.values())
tup = []
for k,v in hashmap.items():
  if v == max_num:
    tup.append(k)
tup.sort()
for i in tup:
  print(i)