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

import numpy as np
from numba import njit


@njit('i8(i8, i8[:])', cache=True)
def solve(n, div):
    for i in range(2, n + 1):
        div[i::i] += 1
    return (div * np.arange(n + 1)).sum()


n = int(input())
div = np.ones(n + 1, dtype=np.int64)
print(solve(n, div))

### FIXED CODE ###

n = int(input())
div = [1] * (n + 1)

for i in range(2, n + 1):
    cnt = 1
    while i * cnt <= n:
        div[i * cnt] += 1
        cnt += 1
print(sum([x * y for x, y in enumerate(div)]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n+1)]


def dp(i, j):
    if j <= i:
        DP[i][j] = 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]


print(dp(0, n))


### FIXED CODE ###

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

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
e = []
for i in a:
    for j in b:
        e.append(i + j)
e = sorted(e, reverse=True)[:k]
ans = []
for i in e:
    for j in c:
        ans.append(i + j)
ans = sorted(ans, reverse=True)[:k]
for i in ans:
    print(i)

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
e = []
for i in a:
    for j in b:
        e.append(i + j)
e = sorted(e, reverse=True)[:k]
ans = []
for i in e:
    for j in c:
        ans.append(i + j)
ans = sorted(ans, reverse=True)[:k]
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
wa = 0
for i in range(N-1):
    for m in A[i+1:]:
        wa += A[i] * m
answer = wa % (10**9+7)
print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
wa = 0
a = 0
for l in range(N-1):
    a += A[N-l-1]
    wa += a * A[N-l-2]
print(wa % (10**9+7))
### BUGGY CODE ###

from collections import Counter

N = int(input())

# s = [''.join(sorted(str(input()))) for _ in range(N)]
# #print(s)
# count = 0
# for i in range(N):
#     for j in range(i+1,N):
#         #diff = Counter(s[i])-Counter(s[j])
#         diff = s[i].replace(s[j],'')
#         if len(diff) == 0:
#             count += 1
        
# print(count)
lst = []
count = 0
for i in range(N):
    s = ''.join(sorted(str(input())))
    #print(s,lst)
    if s in lst:
        count += Counter(lst)[s]
    lst.append(s)
print(count)

### FIXED CODE ###

from collections import Counter
 
n = int(input())
s = [list(input()) for _ in range(n)]
for i in range(n):
    s[i].sort()
    s[i] = ''.join(s[i])
counter = Counter(s)
#print(counter)
ans = 0
for val in counter.values():
    #countC2
    ans += val*(val-1)//2
    
print(ans)
### BUGGY CODE ###

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

h = sorted(h, reverse=True)

try:
    for i in range(k):
        h.pop(0)
except IndexError:
    pass

print(sum(h) if h != 0 else 0)

### FIXED CODE ###

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

h = sorted(h, reverse=True)

del h[:k]

print(sum(h) if h != 0 else 0)
### BUGGY CODE ###

N = int(input())
S = input()
List_R,List_G,List_B = [],[],[]
for i,j in enumerate(S):
  if j == 'R':
    List_R.append(i+1)
  elif j == 'G':
    List_G.append(i+1)
  else:
    List_B.append(i+1)
count = 0
for i in List_R:
  for j in List_G:
    for k in List_B:
      aa = [i,j,k]
      aa.sort()
      if aa[2]-aa[1] != aa[1]-aa[0]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
abc = S.count('R')*S.count('G')*S.count('B')
L = (N-1)//2
for i in range(1,L+1):
  for j in range(N-2*i):
    if S[j]!=S[j+i] and S[j+i]!=S[j+2*i] and S[j]!=S[j+2*i]:
      abc -= 1
print(abc)
### BUGGY CODE ###


lis = []

N,M = [int(i) for i in input().split()]
M_ = M
i = 2

while True:
    if M % i == 0:
        M = M // i
        lis.append(i)
    elif M == 1:
        break
    else:
        i += 1
ans = M_

for n in range(2**len(lis)):
    m = bin(n)[-1:1:-1]
    ret = 1
    for l in range(len(m)):
        if int(m[l]):
            ret *= lis[l]
           # print(lis[l])
            if  ret >= N:
                break
    if ret >= N:
        #print(ret)
        ans = min(ans,ret)

print(M_//ans)


### FIXED CODE ###

import  math
lis = []

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

for i in range(1,int(math.sqrt(M))):
    if M % i == 0:
        lis.append(i)
        lis.append(M//i)


lis.sort()
i =1
for i in lis:
    if i >= N:
        break

print(M//i )
### BUGGY CODE ###

N = int(input())
a_s = input().split(" ")
a_s = list(map(int, a_s))

mod = 10**9 +7
ans = 0
for i in range(len(a_s)-1):
  ans += ((sum(a_s[i+1:])%mod)*a_s[i])%mod
  if ans > mod:
    ans = ans%mod
      
print(ans)

### FIXED CODE ###

N = int(input())
a_s = input().split(" ")
a_s = list(map(int, a_s))
asum = sum(a_s)

mod = 10**9 +7
ans = 0
for i in range(len(a_s)-1):
  asum -= a_s[i]
  ans += (asum*a_s[i])%mod
  if ans > mod:
    ans = ans%mod
      
print(ans)
### BUGGY CODE ###

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)
val1 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)

val2 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)  
ans = wa - val1 -val2
for i in range(10000):
    if ans < 0:
        ans += 10 ** 9 + 7
    else:
        break
print(ans)

### FIXED CODE ###

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)
val1 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)

val2 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

ans = wa - val1 - val2
for i in range(100):
    if ans < 0:
        ans += 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")

### FIXED CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")
### BUGGY CODE ###

from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)


### FIXED CODE ###

from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)
### BUGGY CODE ###

N = int(input())

# 初期化
G = {}  # グラフ
U = {}  # 入次数
D = {}  # 根からの距離
for i in range(N):
    for j in range(i + 1, N):
        G[(i, j)] = set()
        U[(i, j)] = 0
        D[(i, j)] = 0


# グラフを構築
for i in range(N):
    A = list(map(int, input().split()))
    A = [a - 1 for a in A]
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[(fv1, fv2)].add((tv1, tv2))


# 入次数をカウント
for key, value_set in G.items():
    for value in value_set:
        U[value] += 1


# トポロジカルソート
U_zero_nodes = []
for key, value in U.items():
    if value == 0:
        U_zero_nodes.append(key)

topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for to in G[n]:
        U[to] -= 1
        if U[to] == 0:
            U_zero_nodes.append(to)

# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for to in G[t_n]:
        D[to] = max(D[to], D[t_n] + 1)
print(max(D.values()) + 1)


### FIXED CODE ###

N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    start = i + A[i]
    for j in range(start,N):
        if A[j] == j-start:
            count = count + 1
print(count)


### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
diff = [0]*N
summ = [0]*N
count = 0
for i in range(N):
    diff[i] = i - A[i]
    summ[i] = A[i] + i

c_diff = collections.Counter(diff)
c_summ = collections.Counter(summ)
for k in c_diff.keys():
    count = count + c_diff[k]*c_summ[k]
print(count)
### BUGGY CODE ###

R,C,K = map(int,input().split())
item = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int,input().split())
    item[r-1][c-1] = v
    

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

for ri in range(R):
    for ci in range(C):
        dp[ri+1][ci+1][0] = max(dp[ri+1][ci][0], dp[ri][ci+1][3])
        dp[ri+1][ci+1][1] = max(dp[ri+1][ci][1], dp[ri+1][ci][0]+item[ri][ci], dp[ri][ci+1][3]+item[ri][ci], dp[ri+1][ci+1][0])
        dp[ri+1][ci+1][2] = max(dp[ri+1][ci][2], dp[ri+1][ci][1]+item[ri][ci], dp[ri+1][ci+1][1])
        dp[ri+1][ci+1][3] = max(dp[ri+1][ci][3], dp[ri+1][ci][2]+item[ri][ci], dp[ri+1][ci+1][2])

print(dp[-1][-1][3])

### FIXED CODE ###

import sys
import numpy as np
from numba import njit,i8

R,C,K = map(int,input().split())
item = np.zeros((R,C),np.int64)
for _ in range(K):
    r,c,v = map(int,input().split())
    item[r-1][c-1] = v
    

@njit(i8(i8[:,:],i8,i8), cache = True)
def solve(item,R,C):
    dp = np.zeros((R+1,C+1,4),np.int64)
    for ri in range(R):
        for ci in range(C):
            dp[ri+1][ci+1][0] = max(dp[ri+1][ci][0], dp[ri][ci+1][3])
            dp[ri+1][ci+1][1] = max(dp[ri+1][ci][1], dp[ri+1][ci][0]+item[ri][ci], dp[ri][ci+1][3]+item[ri][ci], dp[ri+1][ci+1][0])
            dp[ri+1][ci+1][2] = max(dp[ri+1][ci][2], dp[ri+1][ci][1]+item[ri][ci], dp[ri+1][ci+1][1])
            dp[ri+1][ci+1][3] = max(dp[ri+1][ci][3], dp[ri+1][ci][2]+item[ri][ci], dp[ri+1][ci+1][2])
        

    return dp[-1][-1][3]

print(solve(item,R,C))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
import numpy as np
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

### FIXED CODE ###


from itertools import accumulate
def resolve():

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

    for _ in range(K):
        imos_table = [0]*(N+1)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = list(accumulate(imos_table))[:-1]
        if all([True if a == N else False for a in A]):
            print(*A)
            return
    else:
        print(*A)

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

import numpy as np

import sys

N = int(input())
x = []
y = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


cost = 0
towngroup = np.array(list(range(N)))
for c, i, j in sorted(useful_road):
    if towngroup[i] == towngroup[j]:
        continue
    cost += c

    towngroup[towngroup == towngroup[j]] = towngroup[i]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()


### FIXED CODE ###

import sys

import numpy as np


class Graph:
    def __init__(self, N):
        self.townarrow = [i for i in range(N)]

    def find(self, x):
        if x == self.townarrow[x]:
            return x
        else:
            self.townarrow[x] = self.find(self.townarrow[x])
            return self.townarrow[x]

    def union(self, x, y):
        self.link(self.find(x), self.find(y))

    def link(self, x, y):
        self.townarrow[y] = x


N = int(input())
x = []
y = []
for i in range(N):
    a, b = map(int, input().split())
    x.append(a)
    y.append(b)

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


m = 0
cost = 0
towngroup = Graph(N)
for c, i, j in sorted(useful_road):
    if towngroup.find(i) == towngroup.find(j):
        continue
    cost += c
    m += 1

    towngroup.union(i, j)

    if m == N - 1:
        print(cost)
        sys.exit()
### BUGGY CODE ###

k,s=map(int,input().split())
l=set(range(k+1))
count=0
for i in l:
    for j in l:
        for k in l:
            if i+j+k==s:
                count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
l=list(range(k+1))
count=0
for i in l:
    for j in l:
        q=s-i-j
        if 0<=q<=k:
            count+=1
            
print(count)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0

for i in range(1, K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      ans += gcd(i, j, k)

print(ans)

### FIXED CODE ###

import math
from functools import reduce

K = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0

for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if i == k:
        ans += gcd(i, j, k)
      elif i == j or j == k:
        ans += 3 * gcd(i, j, k)
      else:
        ans += 6 * gcd(i, j, k)

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

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
visited = [[-2]*(w+2) for i in range(h+2)]
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]==".":
			visited[i][j] = -1

delta1 = [[0,1],[1,0],[-1,0],[0,-1]]

q = {(ch,cw)}
set_list = set()
cost = 0
while 1:
	if len(q)==0:
		break
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		for dx,dy in delta1:
			x2 = x+dx
			y2 = y+dy
			if visited[x2][y2]==-1:
				q.add((x2,y2))
	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for dx in range(-2,3):
			for dy in range(-2,3):
				x2 = x+dx
				y2 = y+dy
				if visited[min(x2,h+1)][min(y2,w+1)]!=-1: continue
				q.add((x2,y2))

print(visited[dh][dw])

### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

def p(arr):
	print("_______________________")
	for i in arr:
		for j in i:
			print(j,end=" ")
		print()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = [["#" for i in range(w+2)]]+[["#"]+ list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]

q = deque()
visited = [[-1]*(w+2) for i in range(h+2)]
count = (w+2)*(h+2)
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]=="#":
			visited[i][j] = float("inf")
			count -= 1

from pprint import pprint
visited[ch][cw] = 0

q = {(ch,cw)}
set_list = set()
cost = 0
while count:
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		count-=1
		if s[x-1][y]=="." and visited[x-1][y]==-1:
			q.add((x-1,y))
		if s[x][y-1]=="." and visited[x][y-1]==-1:
			q.add((x,y-1))
		if s[x+1][y]=="." and visited[x+1][y]==-1:
			q.add((x+1,y))
		if s[x][y+1]=="." and visited[x][y+1]==-1:
			q.add((x,y+1))

	if len(set_list)==0:
		break

	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for dx in range(-2,3):
			for dy in range(-2,3):
				x2 = x+dx
				y2 = y+dy
				if visited[min(x2,h+1)][min(y2,w+1)]!=-1: continue
				q.add((x2,y2))

print(visited[dh][dw])
### BUGGY CODE ###

n,w=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(n)]

dp=[]
for y in range(n+1):
    l=[]
    if y==0:dp.append([0]*(w+1));continue
    for x in range(w+1):
        if x==0:l.append(0);continue
        
        now_weight=x
        up_value=dp[-1][now_weight]

        index_weight=a[y-1][0]
        index_value=a[y-1][1]

        blank_weight=max(0,now_weight-index_weight)
        blank_max_value=dp[-1][blank_weight]
        

        t_value=up_value
        if now_weight>=index_weight:t_value=max(blank_max_value+index_value,up_value) 
        
        l.append(t_value)
        
    dp.append(l)

print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(n)]

dp=[]
for y in range(n+1):
    l=[]
    if y==0:dp.append([0]*(w+1));continue
    for x in range(w+1):
        if x==0:l.append(0);continue
        
        now_weight=x
        up_value=dp[-1][now_weight]

        index_weight=a[y-1][0]
        index_value=a[y-1][1]

        blank_weight=max(0,now_weight-index_weight)
        blank_max_value=dp[-1][blank_weight]
        

        t_value=up_value
        if now_weight>=index_weight:t_value=max(blank_max_value+index_value,up_value) 
        
        l.append(t_value)
        
    dp.append(l)

print(dp[n][w])
### BUGGY CODE ###

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

ans=0
for a in range(1,n+1):
  for b in range(1,n+1):
    d=np.gcd(a,b)
    for c in range(1,n+1):
      ans += np.gcd(c,d)

print(ans)

### FIXED CODE ###

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

ans=0
for a in range(1,n+1):
  for b in range(1,n+1):
    d=np.gcd(a,b)
    if d==1:
      ans+=n
      continue
    if d==2:
      ans+=n//2*3+n%2
      continue
    if d==3:
      ans+=n//3*5+n%3
      continue
    if d==5:
      ans+=n//5*9+n%5
      continue
    for c in range(1,n+1):
      ans += np.gcd(c,d)

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

N = int(input())
X = list(map(int, input().split()))
sx = sorted(X)
lm = sx[N//2-1]
rm = sx[N // 2]
for i in range(N):
    if sx.index(X[i]) <= N//2 -1:
        print(rm)
    else:
        print(lm)


### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
sx = sorted(X)
lm = sx[N//2-1]
rm = sx[N // 2]
for i in range(N):
    if X[i] <= lm:
        print(rm)
    else:
        print(lm)
### BUGGY CODE ###

n=int(input())
num=[]
def ap(num1):
    num.append(num1)
def rm(num2):
    num.remove(num2)
for i in range(n):
    a=int(input())
    str=a in num
    if str==True:
        rm(a)
    else:
        ap(a)
print(len(num))


### FIXED CODE ###

n=int(input())
num=[]
def ap(num1):
    num.append(num1)
for i in range(n):
    a=int(input())
    ap(a)
num.sort()
num1=num[0]
num2=1
ans=0
for i in range(n-1):
    if num[i+1]==num1:
        num2+=1
    else:
        num1=num[i+1]
        if num2%2==1:
            ans+=1
        num2=1
if num2%2==1:
    ans+=1
print(ans)