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

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
inputs = []
for _ in range(m):
    h, w = map(int, input().split())
    inputs.append([h,w])
    if h_l[h] :
        h_l[h][1].append(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, [w]]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    elif h_l[h][0] == max_h:
        max_h_l.append(h)
 
        
    if w_l[w]:
        w_l[w][1].append(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, [h]]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    elif w_l[w][0] == max_w:
        max_w_l.append(w)
 
inputs.sort()
max_h_l.sort()

flag = 0
ans = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if flag == 1:
            break
        if [i,j] not in inputs:
            ans = max_h + max_w
            flag = 1
        else:
            ans = max_h + max_w - 1
print(ans)


### FIXED CODE ###

h, w, m = map(int, input().split())
h_l = [[] for i in range(h + 1)]
w_l = [[] for i in range(w + 1)]
max_h = 0
max_h_l = []
max_w = 0
max_w_l = []
inputs = {}
for _ in range(m):
    h, w = map(int, input().split())
    inputs.setdefault(h, set([w]))
    inputs[h].add(w)

    if h_l[h] :
        h_l[h][1].add(w)
        h_l[h][0] += 1
    else:
        h_l[h] = [1, set([w])]
        
    if h_l[h][0] > max_h:
        max_h_l = [h]
        max_h = h_l[h][0]
    elif h_l[h][0] == max_h:
        max_h_l.append(h)
 
        
    if w_l[w]:
        w_l[w][1].add(h)
        w_l[w][0] += 1
    else:
        w_l[w] = [1, set([h])]
    if w_l[w][0] > max_w:
        max_w_l = [w]
        max_w = w_l[w][0]
    elif w_l[w][0] == max_w:
        max_w_l.append(w)

ans = max_h + max_w -1
flag = 0
for i in max_h_l:
    if flag == 1:
        break
    for j in max_w_l:
        if j not in inputs[i]:
            ans = max_h + max_w
            flag = 1
            break
        
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = []
    i = 0
    while i != W:
        if S[y][i] == ".":
            n = 0
            while i < W and S[y][i] == '.':
                i += 1
                n += 1
            ___ = 0
            while ___ < n:
                Hor[y].append(n)
                ___ += 1
        else:
            Hor[y].append(0)
            i += 1
    y += 1

Ver = [0]*W
x = 0
while x != W:
    Ver[x] = []
    i = 0
    while i != H:
        if S[i][x] == ".":
            n = 0
            while i < H and S[i][x] == '.':
                i += 1
                n += 1
            ___ = 0
            while ___ < n:
                Ver[x].append(n)
                ___ += 1
        else:
            Ver[x].append(0)
            i += 1
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

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

from bisect import bisect_left

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

count = 0
length_list.sort()

for a_idx in range(n - 2):
    for b_idx in range(a_idx + 1, n - 1):
        a = length_list[a_idx]
        b = length_list[b_idx]
        if b > a:
            a, b = b, a
        
        left_count = bisect_left(length_list, a+b)
        count += max(0, left_count - b_idx - 1)


print(count)

### FIXED CODE ###

from bisect import bisect_left

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

count = 0
length_list.sort()

for a_idx in range(n - 2):
    for b_idx in range(a_idx + 1, n - 1):
        a = length_list[a_idx]
        b = length_list[b_idx]

        left_count = bisect_left(length_list, a+b)
        count += max(0, left_count - b_idx - 1)


print(count)
### BUGGY CODE ###

import sys
H, W, M = map(int, input().split())
lis =[]
Hlis = [0]*H
Wlis = [0]*W
for _ in range(M):
    Ch, Cm = map(int, input().split())
    Hlis[Ch-1] += 1
    Wlis[Cm-1] += 1
    lis.append([Ch, Cm])

Hmax = max(Hlis)
Hidx = [i+1 for i, v in enumerate(Hlis) if v == Hmax]
Wmax = max(Wlis)
Widx = [i+1 for i, v in enumerate(Wlis) if v == Wmax]

for i in range(len(Hidx)):
    for j in range(len(Widx)):
        if [Hidx[i], Widx[j]] not in lis:
            print(Hmax+Wmax)
            sys.exit()
else:
    print(Hmax + Wmax -1)

### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
lis =set()
Hlis = [0]*H
Wlis = [0]*W
for _ in range(M):
    Ch, Cm = map(int, input().split())
    Hlis[Ch-1] += 1
    Wlis[Cm-1] += 1
    lis.add((Ch, Cm))

Hmax = max(Hlis)
Hidx = [i+1 for i, v in enumerate(Hlis) if v == Hmax]
Wmax = max(Wlis)
Widx = [i+1 for i, v in enumerate(Wlis) if v == Wmax]

for i in range(len(Hidx)):
    for j in range(len(Widx)):
        if (Hidx[i], Widx[j]) not in lis:
            print(Hmax+Wmax)
            sys.exit()
else:
    print(Hmax + Wmax -1)
### BUGGY CODE ###

n,m=map(int,input().split())
l=["p"]
i=0
while len(l)<m:
  i+=1
  l=["b"]+l+["p"]+l+["b"]
for j in range(n-i):
  l=["b"]+l
c=0
for i in range(m):
  if l[i]=="p":
    c+=1
print(c)

### FIXED CODE ###

n,x=map(int,input().split())
plist=[1]
blist=[1]
for i in range(n):
  plist.append(plist[-1]*2+1)
  blist.append(blist[-1]*2+3)
def patty(n,x):
  if n==0:
    return 1
  else:
    if x==1:
      return 0
    elif 1<x and x<=blist[n-1]+1:
      return patty(n-1,x-1)
    elif x==blist[n-1]+2:
      return plist[n-1]+1
    elif 2+blist[n-1]<x and 2*blist[n-1]+2>=x:
      return plist[n-1]+patty(n-1,x-2-blist[n-1])+1
    else:
      return plist[n]
print(patty(n,x))
### BUGGY CODE ###

import itertools, math

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

adj = [[float('inf')] * (N + 1) for _ in range(N + 1)]

for m in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = min(adj[A][B], C)
    adj[B][A] = min(adj[B][A], C)

res = float('inf')

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

for perm in itertools.permutations(r):
    best = 0
    for x, y in zip(perm, perm[1:]):
        best += adj[x][y]
    res = min(res, best)

print(res)

### FIXED CODE ###

import itertools, math

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

adj = [[float('inf')] * (N + 1) for _ in range(N + 1)]

for m in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = min(adj[A][B], C)
    adj[B][A] = min(adj[B][A], C)

res = float('inf')

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

for perm in itertools.permutations(r):
    best = 0
    for x, y in zip(perm, perm[1:]):
        best += adj[x][y]
    res = min(res, best)

print(res)
### BUGGY CODE ###

import sys

N, K = (int(x) for x in input().split())
H = list(map(int, input().split()))
ans=0

if K>=N:
  print(0)
  sys.exit(0)
  
H.sort(reverse=True)
for i in range(K):
  del H[0]
for i in range(len(H)):
  ans+=H[i]
print(ans)

### FIXED CODE ###

import sys

N, K = (int(x) for x in input().split())
H = list(map(int, input().split()))
ans=0

if K>=N:
  print(0)
  sys.exit(0)
  
H.sort(reverse=True)
del H[0:K]
for i in range(len(H)):
  ans+=H[i]
print(ans)
### BUGGY CODE ###

def solve(N, K, heights):
  dp = [0] * N
  for i in range(1, N):
    min_cost = float('inf')
    for k in range(max(0, i - K), i):
      min_cost = min(min_cost, dp[k] + abs(heights[i] - heights[k]))
    dp[i] = min_cost
  print(dp[N - 1])

 
def iin(): return int(input())
def iln(): return list(map(int, input().split()))
 
N, K = iln()
solve(N, K, iln())


### FIXED CODE ###

def solve(N, K, heights):
  dp = [0] * N
  for i in range(1, N):
    min_cost = float('inf')
    for k in range(max(0, i - K), i):
      # min_cost = min(min_cost, dp[k] + abs(heights[i] - heights[k]))
      temp = dp[k] + abs(heights[i] - heights[k])
      if temp < min_cost:
        min_cost = temp
    dp[i] = min_cost
  print(dp[N - 1])


 
def iin(): return int(input())
def iln(): return list(map(int, input().split()))
 
N, K = iln()
solve(N, K, iln())
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
L=[0]*Q
P=[0]*Q
for i in range(Q):
	L[i],P[i]=map(int,input().split())
for i in range(Q):
	count=0
	D=S[L[i]-1:P[i]]
	print(D.count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
X=[0]*N
for i in range(N-1):
	if S[i:i+2]=="AC":
		X[i+1]=X[i]+1
	else:
		X[i+1]=X[i]
for i in range(Q):
	L,R=map(int,input().split())
	print(X[R-1]-X[L-1])
### BUGGY CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

dist = abs(b - a)
mys = v - w

for i in range(t):
  dist -= mys
  if dist <= 0:
    print("YES")
    exit()
print("NO")

### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

dist = abs(b - a)
mys = v - w

if mys * t >= dist:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

import numpy as np

N = int(input())
X = [int(i) for i in input().split()]

for i in range(0, N):
    tmp_list = []
    if i==0:
        tmp_list = []
    else:
        tmp_list = X[:i]
    tmp_list.extend(X[i+1:])
    med = np.median(tmp_list)
    print(int(med))

### FIXED CODE ###

import numpy as np
import copy

N = int(input())
X = [int(i) for i in input().split()]

max_value = max(X)
min_value = min(X)

tmp_list = copy.deepcopy(X)
tmp_list.sort()
all_med = tmp_list[int((len(tmp_list)+1) / 2) - 1]

tmp_list.remove(max_value)
min_med = tmp_list[int((len(tmp_list)+1) / 2) - 1]

tmp_list = copy.deepcopy(X)
tmp_list.remove(min_value)
tmp_list.sort()
max_med = tmp_list[int((len(tmp_list)+1) / 2) - 1]

for i in range(N):
    if X[i] <= all_med:
        print(int(max_med))
    else:
        print(int(min_med))
### BUGGY CODE ###

n = int(input())
P = [int(i) for i in input().split()]
r = 1
for i in range(1, n):
    if P[i] < min(P[:i]):
        r += 1
print(r)

### FIXED CODE ###

n = int(input())
P = [int(i) for i in input().split()]
r = 0
m = n+1
for i in range(n):
    if P[i] < m:
        r += 1
        m = P[i]
print(r)
### BUGGY CODE ###

import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
ans = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) in m.keys():
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp

print(int(ans))

### FIXED CODE ###

import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
flag = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) not in m.keys():
            flag = 1
            break

if flag == 1:
    print(int(h_max + w_max))
else:
    print(int(h_max + w_max - 1))
### BUGGY CODE ###

n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()))
time = [f[i] * a[-i-1] for i in range(n)]

sup = max(time)
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = sum([(max([0, time[i] - x]) + f[i] - 1) // f[i] for i in range(n)])
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.sort(np.array(input().split(), dtype=np.int))
f = np.sort(np.array(input().split(), dtype=np.int))
time = f * a[::-1]

sup = time.max()
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = ((np.maximum(time - x, 0) + f - 1) // f).sum()
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n,m,s,t=map(int,input().split())
s,t=s-1,t-1
edges=[list(map(int,input().split())) for _ in range(m)]
row=[]
col=[]
data1=[]
data2=[]
for u,v,a,b in edges:
  row.append(u-1)
  col.append(v-1)
  data1.append(a)
  data2.append(b)
g1=csr_matrix((data1,(row,col)),shape=(n,n))
g2=csr_matrix((data2,(row,col)),shape=(n,n))
d1=dijkstra(g1,directed=False,indices=s)
d2=dijkstra(g2,directed=False,indices=t)
ans=[10**18]*n
for i in range(n-1,-1,-1):
  tmp=int(d1[i])+int(d2[i])
  ans[i]=min(tmp,ans[i])
  if i!=n-1:
    ans[i]=min(ans[i],ans[i+1])
maxs=10**15
for i in range(n):
  print(maxs-ans[i])

### FIXED CODE ###

import sys
input=sys.stdin.readline

import heapq

def dijkstra(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m,s,t=map(int,input().split())
s,t=s-1,t-1
edge1=[[] for _ in range(n)]
edge2=[[] for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  edge1[u-1].append([a,v-1])
  edge1[v-1].append([a,u-1])
  edge2[u-1].append([b,v-1])
  edge2[v-1].append([b,u-1])
d1=dijkstra(s,edge1)
d2=dijkstra(t,edge2)
INF=10**15
ans=[INF]*n
ans[n-1]=int(d1[n-1]+d2[n-1])
for i in range(n-2,-1,-1):
  tmp=int(d1[i]+d2[i])
  ans[i]=min(tmp,ans[i+1])
for i in range(n):
  print(INF-ans[i])
### BUGGY CODE ###

from functools import reduce
from math import factorial

N = int(input())

def func(x):
    n = x
    if n % 2 == 0:
        num = str(2 ** (n // 2) * factorial(n // 2))
        ans = len(num) - len(num.rstrip("0"))
        return ans
    else:
        return 0

print(func(N))

### FIXED CODE ###

N = int(input())


def func(x):
    n = x
    if n < 5:
        return 0
    if n % 2 == 0:
        cnt = 0
        i = 1
        n = n // 2
        while 5 ** i <= x:
            n = n // 5
            cnt += n
            i += 1

        return cnt

    else:
        return 0


print(func(N))
### BUGGY CODE ###

n=int(input())
p=map(int,input().split())
p_list=list(p)
n_list=[]
for j in range(n):
    for i in range(j,n):
        if p_list[i]<=p_list[j]:
            n_list.append(i)
count=0
for i in range(n):
    if i+1==n_list.count(i):
        count+=1
print(count)

            

### FIXED CODE ###

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

num = 2*10**5+1
ans = 0
for i in range(n):
    if P[i] <= num:
        num = P[i]
        ans += 1
        
print(ans)
### BUGGY CODE ###

import functools
import operator

n=input()
a=list(map(int,input().split()))
ans= functools.reduce(operator.mul, a)

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

### FIXED CODE ###

n=input()
A=list(map(int,input().split()))
ans=1
if A.count(0)==0:
  for i in A:
    ans*=i
    if ans>10**18:
      ans=-1
      break
else:
  ans=0
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
g=[]
for i in range(m):
  l,r=map(int,input().split())
  g_list=[]
  for j in range(l,r+1):
    g_list.append(j)
  g.append(g_list)

for k in range(m):

  if k == 0:
    unq=set(g[0])
  else:
    unq=unq&set(g[k])

print(len(list(unq)))


### FIXED CODE ###

n,m=map(int,input().split())
l=[]
r=[]
for i in range(m):
  li,ri=map(int,input().split())
  l.append(li)
  r.append(ri)
 
l_max=max(l)
r_min=min(r)
 
if r_min < l_max:
  print(0)
else:
  print(r_min-l_max+1)
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
b = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [list(input()) for i in hs]
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append([i, j])
    memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

### FIXED CODE ###

from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
n = int(input())
a = list(map(int,input().split()))

ans = 10**18
prod = 1
f = 0
f2 = 0

for i in range(n):
    prod *= a[i]
    if a[i] == 0:
        f = 1
        break

if f == 1:
    print(0)

else:
    if prod > ans:
        print(-1)
    else:
        print(prod)
    

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = 1000000000000000000
prod = 1
f = 0
f2 = 0

for i in range(n):
    if a[i] == 0:
        f = 1
        break

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

    if prod > ans:
        f2 = 1
        break

if f == 1:
    print(0)

else:
    if f2 == 1:
        print(-1)
    else:
        print(prod)
### BUGGY CODE ###

from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

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

n = 0
C = set(A)

for k in C:
    cnt = A.count(k)
    n +=  cnt * (cnt-1) // 2

for i in range(N):
    a = A[i]
    print(n - A.count(a) + 1)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

n = 0
B = set(A)

C = Counter(A)

for i in C.keys():
    n += C[i] * (C[i]-1) // 2

for i in range(N):
    a = A[i]
    print(n - C[a] + 1)
### BUGGY CODE ###


def main():
    H, W = map(int, input().split()) # 横に2個
    checked = [[False if a == '.' else True for a in list(input()+'#')] for i in range(H)]
    checked.extend([[True]*(W+1)])
    qs = [(h, w) for h in range(H) for w in range(W) if checked[h][w]]

    c = 0
    for _ in range(2000):
        qqs = []
        for h,w in qs:
            checked[h][w] = True
            if not checked[h-1][w]:
                qqs.append((h-1, w))
            if not checked[h+1][w]:
                qqs.append((h+1, w))
            if not checked[h][w-1]:
                qqs.append((h, w-1))
            if not checked[h][w+1]:
                qqs.append((h, w+1))
        if not qqs:
            break
        c += 1
        qs = qqs

    print(c)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


if __name__ == "__main__":
    main()