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

import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


N = int(input())
x_list = [0] * N
y_list = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = [x, i]
    y_list[i] = [y, i]

x_list.sort()
y_list.sort()
adj = [0] * (2 * (N-1))
for i in range(N-1):
    adj[2*i] = [x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]]
    adj[2*i+1] = [y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]]

print(kruskal(adj, N))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

s = input()
len_s = len(s)
INF = 1e10
memo_ls = [[0 if j < (i+3)//2 else -INF for j in range(len_s)] for i in range(len_s)]
# memo_ls[i][j] : i回目までにj回パーを出した場合の得点
for i, enemy in enumerate(s):
    if i == 0:
        memo_ls[0][0] = -1 if enemy == "p" else 0
        continue
    for j in range((i+3)//2):
        if j == 0:
            memo_ls[i][j] = memo_ls[i-1][0] if enemy == "g" else memo_ls[i-1][0] - 1
            continue
        if enemy == "g":
            memo_ls[i][j] = max(memo_ls[i-1][j-1]+1, memo_ls[i-1][j])
        else:
            memo_ls[i][j] = memo_ls[i-1][j] - 1
print(max(memo_ls[-1]))

### FIXED CODE ###

s = input()
len_s = len(s)
cnt = 0
enemy = []
me = []
INF = 1e10
for i, _s in enumerate(s):
    if _s == "p":
        cnt += 1
    enemy.append(cnt)
    me.append((i+1) // 2)
    diff = (i + 1) // 2 - cnt
print(diff)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    print(max(a[:i] + a[i + 1:]))


### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(copy.copy(a), reverse=True)

for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

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

for _ in range(M):
    i = A.index(max(A))
    a=A[i]>>1
    A[i]=a

print(sum(A))

### FIXED CODE ###

from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    N,M=[int(x) for x in input().split()]
    A=[-int(x) for x in input().split()]

    heapq.heapify(A)
    for _ in range(M):
        a = -heapq.heappop(A) // 2 # 最小値取得
        heapq.heappush(A, -a)
    
    print(-sum(A))

main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(map(int,input().split()))
C=Counter(A)
c1,c2,c3=[C[i] for i in (1,2,3)]
DP=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)] 
DP[0][0][0]=0
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i:
                tmp+=DP[k][j+1][i-1]*i
            if j:
                tmp+=DP[k+1][j-1][i]*j
            if k:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])
### BUGGY CODE ###

n = int(input())
xys = [list(map(int, input().split())) + [i] for i in range(n)]
edges = []
xys.sort()
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((x2 - x1, index1, index2))

xys.sort(key=lambda x:x[1])
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((y2 - y1, index1, index2))

parent = [i for i in range(n)]
def find(x):
    if x == parent[x]:return x
    parent[x] = find(parent[x])
    return parent[x]

edges.sort()
ans = 0
for cost, index1, index2 in edges:
    p1, p2 = find(index1), find(index2)
    if p1 != p2:
        parent[p1] = p2
        ans += cost
print(ans)

### FIXED CODE ###

n = int(input())
xys = [list(map(int, input().split())) + [i] for i in range(n)]
edges = []
xys.sort()
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((x2 - x1, index1, index2))

xys.sort(key=lambda x:x[1])
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((y2 - y1, index1, index2))

parent = [i for i in range(n)]
def find(x):
    if x == parent[x]:return x
    parent[x] = find(parent[x])
    return parent[x]

edges.sort()
ans = 0
for cost, index1, index2 in edges:
    p1, p2 = find(index1), find(index2)
    if p1 != p2:
        parent[p1] = p2
        ans += cost
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.insert(0,0)
A.append(0)
ans=0

for i in range(1,N+1):
    for j in range(1, N + 2, 1):
        ans += abs(A[j] - A[j - 1])
    if A[i+1]<A[i-1]:
        if A[i-1]<A[i]:
            ans-=2*abs(A[i-1]-A[i])
        if A[i]<A[i+1]:
            ans-=2*abs(A[i+1]-A[i])
    if A[i-1]<A[i+1]:
        if A[i+1]<A[i]:
            ans-=2*abs(A[i]-A[i+1])
        if A[i]<A[i-1]:
            ans-=2*abs(A[i-1]-A[i])
    print(ans)
    ans=0

### FIXED CODE ###

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

list=[0]
list += a
list += [0]

sum=0
for i in range(n+1):
    sum += abs(list[i] - list[i+1])

for i in range(1,n+1):
    ans = 0
    ans = sum - abs(list[i] - list[i - 1]) -abs(list[i + 1] - list[i]) + abs(list[i + 1] - list[i - 1])
    print(ans)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n = int(input())
    hp = sorted([tuple(map(int, input().split()))
                 for _ in [0]*n], key=lambda x: x[0]+x[1])
    dp = [10**10]*(n+1)
    dp[0] = 0
    for c, (h, p) in enumerate(hp):
        for k in range(c, -1, -1):
            if dp[k] <= h:
                dp[k+1] = min(dp[k+1], dp[k]+p)
    for i in range(n, -1, -1):
        if dp[i] != 10**10:
            print(i)
            break


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()
### BUGGY CODE ###

s = input()
o = len(s)
while True:
  b = len(s)
  s = s.replace('01','')
  s = s.replace('10','')
  if(len(s) == b):
    break
print(o - len(s))

### FIXED CODE ###

s = input()
z = s.count('0')
if 2*z > len(s):
  print((len(s)-z)*2)
else:
  print(2*z)
### BUGGY CODE ###

K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count+=1
print(count)

### FIXED CODE ###

K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        sumz=S-x-y
        if sumz>=0 and sumz<=K:    
            count+=1
print(count)
### BUGGY CODE ###

def eratosthenes(limit):
    import math
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > math.sqrt(limit): break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
l = eratosthenes(10**5)

d = [0]*(10**5+1)
for i in range(len(l)-1):
    for j in range(i, len(l)):
        if l[i] == (l[j]+1)//2: d[l[j]] += 1
for i in range(1, 10**5+1): d[i] += d[i-1]
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(d[r]-d[l-1])

### FIXED CODE ###

def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > 316: break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
l = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[i] and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    ss = [input() for _ in range(h)]

    matl = [[0 for _ in range(w)] for _ in range(h)]
    matr = [[0 for _ in range(w)] for _ in range(h)]
    matu = [[0 for _ in range(w)] for _ in range(h)]
    matd = [[0 for _ in range(w)] for _ in range(h)]

    for j in range(h):
        for i in range(w):
            if ss[j][i] == '#':
                matd[j][i] = 0
            elif j == 0:
                matd[j][i] = 1
            else:
                matd[j][i] = matd[j - 1][i] + 1

            if ss[h - j - 1][i] == '#':
                matu[h - j - 1][i] = 0
            elif h - j == h:
                matu[h - j - 1][i] = 1
            else:
                matu[h - j - 1][i] = matu[h - j][i] + 1

            if ss[j][i] == '#':
                matr[j][i] = 0
            elif i == 0:
                matr[j][i] = 1
            else:
                matr[j][i] = matr[j][i - 1] + 1

            if ss[j][w - i - 1] == '#':
                matl[j][w - i - 1] = 0
            elif w - i == w:
                matl[j][w - i - 1] = 1
            else:
                matl[j][w - i - 1] = matl[j][w - i] + 1

    maxv = 0
    for j in range(h):
        for i in range(w):
            tmp = matu[j][i] + matd[j][i] + matr[j][i] + matl[j][i]
            if tmp > maxv:
                maxv = tmp
    print(maxv - 3)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, w = map(int, input().split())
    ss = [input() for _ in range(h)]

    matl = [[0 for _ in range(w)] for _ in range(h)]
    matr = [[0 for _ in range(w)] for _ in range(h)]
    matu = [[0 for _ in range(w)] for _ in range(h)]
    matd = [[0 for _ in range(w)] for _ in range(h)]

    for j in range(h):
        for i in range(w):
            if ss[j][i] == '#':
                matd[j][i] = 0
            elif j == 0:
                matd[j][i] = 1
            else:
                matd[j][i] = matd[j - 1][i] + 1

            if ss[h - j - 1][i] == '#':
                matu[h - j - 1][i] = 0
            elif h - j == h:
                matu[h - j - 1][i] = 1
            else:
                matu[h - j - 1][i] = matu[h - j][i] + 1

            if ss[j][i] == '#':
                matr[j][i] = 0
            elif i == 0:
                matr[j][i] = 1
            else:
                matr[j][i] = matr[j][i - 1] + 1

            if ss[j][w - i - 1] == '#':
                matl[j][w - i - 1] = 0
            elif w - i == w:
                matl[j][w - i - 1] = 1
            else:
                matl[j][w - i - 1] = matl[j][w - i] + 1

    maxv = 0
    for j in range(h):
        for i in range(w):
            tmp = matu[j][i] + matd[j][i] + matr[j][i] + matl[j][i]
            if tmp > maxv:
                maxv = tmp
    print(maxv - 3)

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

n=int(input())
l=list(map(int,input().split()))
for i in range(1,n):
    k=l.count(i)
    print(k)
    for _ in range(k):
        l.remove(i)
print(0)


### FIXED CODE ###

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

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[-1 for _ in range(n+1)]
dp[0]=dp[1]=1
def step(s):
    if s in a:
        dp[s]=0
        return
    elif dp[s]>=0:
        return 
    else:
        dp[s]=(dp[s-1]+dp[s-2])%1000000007
        return
for i in range(n+1):
    step(i)
print(dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])
### BUGGY CODE ###

N = int(input())
A = input()
Q = int(input())
for i in range(Q):
    B, C = input().split()
    A = A.replace(B, C)
    print(sum([int(n) for n in A.split()]))


### FIXED CODE ###

from collections import Counter
from decimal import *

N = int(input())
dp = [0]*(10**5+1)
A = []
for n in input().split():
    n = int(n)
    dp[n] += 1
    A.append(n)
ans = sum(A)
Q = int(input())
for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    diff = dp[B] * (C-B)
    ans += diff
    print(ans)
    dp[C] += dp[B]
    dp[B] = 0
### BUGGY CODE ###

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    dics = [{} for _ in range(n)]
    dics[0][color[0]] = 0
    for i in range(1, n):
        dics[i].update(dics[i-1])
        dics[i][color[i]] = i
    for i in range(q):
        qry[i].append(i)
        qry[i].append(0)
    qry.sort(key=lambda x: x[0])
    for i in range(q):
        l, r = qry[i][0]-1, qry[i][1]-1
        rmset = set()
        for v in dics[r].keys():
            if dics[r][v] < l:
                rmset.add(v)
        for v in rmset:
            dics[r].pop(v)
        qry[i][3] = len(dics[r])
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)
### BUGGY CODE ###


#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

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

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])


### FIXED CODE ###


#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

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

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])
### BUGGY CODE ###

from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.append([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.append([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.append([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.append([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)



### FIXED CODE ###

from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)
### BUGGY CODE ###

from collections import Counter
n=int(input())
s=[input() for i in range(n)]
c=Counter(s)
t=[]
v=c.most_common()[0][1]
t.append(c.most_common()[0][0])
for i in range(1,len(c)):
  a=c.most_common()[i][1]
  if v>a:
    break
  else:
    t.append(c.most_common()[i][0])
t.sort()
for i in t:
  print(i)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[input() for i in range(n)]
c=Counter(s)
t=[]
u=c.most_common()
v=u[0][1]
t.append(u[0][0])
for i in range(1,len(c)):
  a=u[i][1]
  if v>a:
    break
  else:
    t.append(u[i][0])
t.sort()
for i in t:
  print(i)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, int((num)/2)+1):
        if gcd(i, num) != 1:
            return False

    return True


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

n=0
for data in listdata:
    ch = check_pn(data)
#    print(data, ch)
    n += ch

print (n)



### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

def check_pn(num):
    if (num <2):
        return False
    elif (num==2):
        return True

    if (num%2 == 0):
        return False
    i = 3
    while (i <= num/i):
        if num % i == 0:
            return False
        i += 2

    return True


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

n=0
for data in listdata:
    ch = check_pn(data)
    n += ch

print (n)