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

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

H, W = list(map(int, input().split()))
G = [list(input()) for i in range(H)]

Visited = [[0] * W for i in range(H)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]


def dfs(ny, nx, color):
    for dy, dx in direction:
        if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
            continue

        if G[ny + dy][nx + dx] == G[ny][nx]:
            continue

        if Visited[ny + dy][nx + dx] != 0:
            continue

        if G[ny + dy][nx + dx] == '#':
            Visited[ny + dy][nx + dx] = color
        else:
            Visited[ny + dy][nx + dx] = -color

        dfs(ny + dy, nx + dx, color)


Color = 1
for y in range(H):
    for x in range(W):
        if Visited[y][x] == 0:
            if G[y][x] == '#':
                Visited[y][x] = Color
            else:
                Visited[y][x] = -Color
            dfs(y, x, Color)
            Color += 1

D = defaultdict(int)
for i in range(1, Color + 1):
    D[i] = 0
    D[-i] = 0

for row in Visited:
    for data in row:
        D[data] += 1

ans = 0
for key in D.keys():
    ans += D[key] * D[-key]

print(ans // 2)


### FIXED CODE ###

def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 9)
    
    H, W = list(map(int, raw_input().split()))
    G = [list(raw_input()) for i in range(H)]
    
    Visited = [[0] * W for i in range(H)]
    direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    
    def dfs(ny, nx, color):
        for dy, dx in direction:
            if not ((0 <= ny + dy < H) and (0 <= nx + dx < W)):
                continue
    
            if G[ny + dy][nx + dx] == G[ny][nx]:
                continue
    
            if Visited[ny + dy][nx + dx] != 0:
                continue
    
            if G[ny + dy][nx + dx] == '#':
                Visited[ny + dy][nx + dx] = color
            else:
                Visited[ny + dy][nx + dx] = -color
    
            dfs(ny + dy, nx + dx, color)
    
    
    Color = 1
    for y in range(H):
        for x in range(W):
            if Visited[y][x] == 0:
                if G[y][x] == '#':
                    Visited[y][x] = Color
                else:
                    Visited[y][x] = -Color
                dfs(y, x, Color)
                Color += 1
    
    D = defaultdict(int)
    for i in range(1, Color + 1):
        D[i] = 0
        D[-i] = 0
    
    for row in Visited:
        for data in row:
            D[data] += 1
    
    ans = 0
    for key in D.keys():
        ans += D[key] * D[-key]
    
    print(ans // 2)
    
main()
### BUGGY CODE ###

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

def prime_factorization(n):
    arr=[]
    temp=n

    for i in range(2,int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp//=i
            arr.append([i,cnt])

    if temp!=1:
        arr.append([temp,1])
    
    if arr==[]:
        arr.append([n,1])
    
    return arr


isPairwise = True
isSetwise = True
dict=defaultdict(lambda:0)

for i in range(N):
    arr = prime_factorization(A[i])
    for j in range(len(arr)):
        prime=arr[j][0]
        if prime!=1:
            dict[prime]+=1

for i in dict.values():
    if i==N:
        isPairwise=False
        isSetwise=False
    elif i>1:
        isPairwise=False
    else:
        pass

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
    


### FIXED CODE ###

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

c=[0]*(10**6+5)

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000005):
    cnt=0
    for j in range(i,1000005,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

g=0
for i in range(N):
    g=gcd(g,A[i])
if g>1:
    isSetwise=False

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

# coding: utf-8
N = int(input())
H = list(map(int, input().split()))
flag = True
top = [-1] * N
for i in range(N):
    if i == 0:
        top[i] = H[i]
    else:
        tmp = top[:i]
        tmp.append(H[i])
        top[i] = max(tmp)
for i, h in enumerate(H):
    if top[i] - h >= 2:
        flag = False
        break
print("Yes" if flag else "No")

### FIXED CODE ###

# coding: utf-8
N = int(input())
H = list(map(int, input().split()))
flag = True
for i in range(1, N):
    if H[i] < H[i-1]:
        flag = False
        break
    else:
        if H[i-1] < H[i]:
            H[i] -= 1
print("Yes" if flag else "No")
### BUGGY CODE ###

a,b = map(int, input().split())
ans = 1
for i in range(a,b+1):
    ans*=i
print('Positive' if ans>0 else 'Zero' if ans == 0 else 'Negative')

### FIXED CODE ###

a,b = map(int, input().split())
if a>0:
    print('Positive')
elif b<0:
    if (b-a)%2==0:
        print('Negative')
    else:
        print('Positive')
else:
    print('Zero')
### BUGGY CODE ###

S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B():
    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            if num_combinations >= MOD:
                num_combinations %= MOD
    print(num_combinations)

focus_on_B()


### FIXED CODE ###

S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])
### BUGGY CODE ###

N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]
works.sort(key=lambda x:(-x[1], -x[0]))
days = [0] * (M+1)
ans = 0
max_day = M+1
for work in works:
  if work[0] > M or work[0] >= max_day:
    continue
  full = True
  for day in range(work[0], max_day):
    if days[day] == 0:
      days[day] = 1
      ans += work[1]
      full = False
      break
  if full:
    max_day = work[0]
print(ans)


### FIXED CODE ###

import heapq

MAX = 10**5+1
N, M = map(int, input().split())
works = [[] for _ in range(MAX)]
for _ in range(N):
  day, reward = map(int, input().split())
  works[day].append(reward)
hp = []
ans = 0
for day in range(1, M+1):
  if len(works[day]) > 0:
    for reward in works[day]:
      heapq.heappush(hp, -reward)
  if len(hp) > 0:
    ans += -heapq.heappop(hp)
print(ans)
### BUGGY CODE ###

n = int(input())
lists = list(map(int, input().split()))
for i in range(1, n+1):
    print(lists.count(i))

### FIXED CODE ###

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

def ACcount(l,r):
    count = 0
    for i in range(l-1,r-1): #最後にAが出ても意味ないのでr-1でカット
        if(S[i]=='A'):
            if(S[i+1]=='C'):
                count += 1
    return count

n,q = map(int,input().split())
S = list(input())
l = [0]*q
r = [0]*q
for i in range(q):
    l,r = map(int,input().split())
    print(ACcount(l,r))
"""
for i in range(q):
    l[i],r[i] = map(int,input().split())

for i in range(q):
    print(ACcount(l[i],r[i]))
"""

### FIXED CODE ###

n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

import sys
import math

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    dp = [float('inf')] * (h+1)

    for point in range(h+1):
        for i in range(n):
            if point <= a[i]:
                dp[point] = min(dp[point], b[i])
                continue

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print(dp[h])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    # max_a = 0
    # ef_i = -1
    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        # max_a = max(max_a, a[i])
        # if a[ef_i] / b[ef_i] < a[i] / b[i]:
        #     ef_i = i

    dp = [float('inf')] * (h+1)

    for point in range(h+1):
        for i in range(n):
            if point <= a[i]:
                dp[point] = min(dp[point], b[i])
                continue

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print(dp[h])


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

n = int(input())
a = list(map(int, input().split())) + ["a"]
t = len(a)
cnt = 0
cur = 0
while t > 2:
  l,r = 0,1
  while a[r] != "a" and a[r] == a[l]:
    r += 1
  if a[r] == "a":
    print(cnt+1)
    exit()
  d = a[r]-a[l]
  while a[r+1] != "a" and (a[r+1]-a[r])*d>=0:
    r += 1
  cnt += 1
  d = 0
  a = a[r+1:]
  t -= r+1
if a[0] != "a":
  cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt,st,d = 0,-1,0
for i in range(n):
  if st < 0:
    st = i
    continue
  elif d == 0:
    if a[i]-a[st] != 0:
      r = i
      d = a[r]-a[st]
    continue
  else:
    if (a[i]-a[i-1])*d < 0:
      cnt += 1
      st,d = i,0
if st != -1:
  cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
ans = 0
light = 0
memo = [0]
while light != 1:
    if a[light]-1 in memo:
        print(-1)
        exit()
    memo.append(a[light]-1)
    light = a[light]-1
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
ans = 0
light = 0
for i in range(10**6):
    light = a[light]-1
    ans += 1
    if light == 1:
        print(ans)
        exit()
print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] = list(format(a[i],'0b').zfill(65))
g = [0 for i in range(65)]
for i in range(65):
    for j in range(n):
        if a[j][i] == '1':
            g[i] += 1
ans = 0
for i in range(len(g)):
    ans += g[i]*(n-g[i])*(pow(2,64-i,10**9+7))
    ans = ans%(10**9+7)
print(int(ans))

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    count = 0
    for j in a:
        if j >> i & 1:
            count += 1
    ans += count * (n-count) * 2** i
print(ans % mod)    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
ans = 0
for i in range(60):
    mask = 1 << i
    count = sum(1 for j in a if mask & j == 0)
    ans += count * (n-count) * pow(2,i,mod)
print(ans % mod)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B=[]
C=[]
for i in range(M):
	b, c = list(map(int, input().split()))
	B.append(b)
	C.append(c)

A.sort()
for i in range(M):
	loc = bisect.bisect_left(A, C[i])
	loc2 = min(B[i], loc)
	A[loc:loc] = [C[i]]*loc2
	A = A[loc2:]
    
print(sum(A))

### FIXED CODE ###



import sys
def input():
	return sys.stdin.readline().strip()

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

CB = []
for i in range(M):
	B, C = list(map(int, input().split()))
	CB.append((C, B))
CB.sort()

sumb = 0
change = []
while sumb <= N and len(CB) > 0:
	C, B = CB.pop()
	sumb += B
	change.extend([C]*B)

change = change[0:N]

for i in range(len(change)):
	if A[i] < change[i]:
		A[i] = change[i]
	else:
		break

print(sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
input()
A = input().split()
ans = 1
for a in A:
    ans*=int(a)
    if ans==0:
        print(0)
        quit()
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
else:
    prod = 1
    for a in A:
        prod*=a
        if prod > 10**18:
            print(-1)
            quit()
    print(prod)
### BUGGY CODE ###

N,W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())
dp = [[int(0) for i in range(W+1)] for i in range(N)]
ans = int(0)
dp[0][0] = 0


for i in range(0,N):
    for j in range(W+1):
        if j==0:
            dp[i][j] = 0
        elif w[i]>j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i - 1][j - w[i]] + v[i]

ans = max(max(dp))

print(ans)

### FIXED CODE ###


N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
	for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(dp[N][W])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int):
    n = list(map(int,list(str(N))))
    pay = []
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay.append(str(n[i]+kuriage))
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay.append("0")
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay.append(str(n[i]+kuriage))
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay.append("0")
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay.append(str(n[i]+kuriage))
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay.append("0") 
                kuriage = 1

    if kuriage == 1:
        pay.append("1")
        pay_count += 1
    
    pay = ''.join(pay[::-1])
    oturi = int(pay)-N
    oturi_count = 0
    
    for i in str(oturi):
        oturi_count += int(i)

    print(pay_count+oturi_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: str):
    n = list(map(int,list(N)))
    kuriage = 0
    LEN = len(n)
    pay_count = 0

    for i in range(LEN-1,-1,-1):
        if i != 0:
            if n[i-1] >= 5:
                if n[i]+kuriage <= 4:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
            else:
                if n[i]+kuriage <= 5:
                    pay_count += n[i]+kuriage
                    kuriage = 0
                else:
                    pay_count += 10-(n[i]+kuriage)
                    kuriage = 1
        else:
            if n[i]+kuriage <= 5:
                pay_count += n[i]+kuriage
                kuriage = 0
            else:
                pay_count += 10-(n[i]+kuriage)
                kuriage = 1

    if kuriage == 1:
        pay_count += 1
    print(pay_count)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)
    solve(N)

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

mod = 998244353
S,K = input().split()
K = min(300,int(K))
a = []
c = 0
for i in range(len(S)):
    if S[i]=='0':
        a.append(c)
        c = 0
    else:
        c += 1
if S[-1]=='1':
    a.append(c)
a = a[::-1]
N = len(a)
dp = [[[0]*(K+1) for _ in range(K+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(K+1):
        for k in range(j+1):
            for l in range(a[i]+1):
                if j+l>K:
                    break
                dp[i+1][j+l][k+l] += dp[i][j][k]
                dp[i+1][j+l][k+l] %= mod
            for l in range(1,k+1):
                dp[i+1][j][k-l] += dp[i][j][k]
                dp[i+1][j][k-l] %= mod
                
ans = 0
for k in range(K+1):
    ans += dp[N][k][0]
    ans %= mod
print(ans)


### FIXED CODE ###

mod = 998244353
S,K = input().split()
a = []
c = 0
for i in range(len(S)):
    if S[i]=='0':
        a.append(c)
        c = 0
    else:
        c += 1
if S[-1]=='1':
    a.append(c)
a = a[::-1]
K = min(sum(a),int(K))
N = len(a)
dp = [[[0]*(K+1) for _ in range(K+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(K+1):
        for k in range(j+1):
            for l in range(a[i]+1):
                if j+l>K:
                    break
                dp[i+1][j+l][k+l] += dp[i][j][k]
                dp[i+1][j+l][k+l] %= mod
            for l in range(1,k+1):
                dp[i+1][j][k-l] += dp[i][j][k]
                dp[i+1][j][k-l] %= mod
                
ans = 0
for k in range(K+1):
    ans += dp[N][k][0]
    ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())

m = {'R': [], 'G': [], 'B': []}

for i, c in enumerate(s):
  if c == 'R':
    m['R'].append(i)
  elif c == 'G':
    m['G'].append(i)
  else:
    m['B'].append(i)

result = len(m['R']) * len(m['G']) * len(m['B'])

for i in range(1, n + 1):
  for j in range(i + 1, n + 1):
    for k in range(j + 1, n + 1):
      if not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
        continue

      if j - i == k - j:
        result -= 1

print(result)

### FIXED CODE ###

n = int(input())
s = list(input())

m = {'R': 0, 'G': 0, 'B': 0}

for i, c in enumerate(s):
  if c == 'R':
    m['R'] += 1
  elif c == 'G':
    m['G'] += 1
  else:
    m['B'] += 1

result = m['R'] * m['G'] * m['B']

for i in range(1, n - 1):
  for j in range(i + 1, n):
    k = 2 * j - i

    if k > n or not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
      continue
    result -= 1

print(result)
### BUGGY CODE ###

import itertools
while True:
    n,s=map(int,input().split())
    if n==0 and s==0:
        break
    ans=0
    comb=itertools.combinations(range(0,s+1),n)
    for c in comb:
        if sum(c) == s:
            ans +=1
    print(ans)


### FIXED CODE ###

def counter(rest, n, acc, to):
  if rest == 0:return acc == to
  if n == 10:return 0 
  return counter(rest - 1, n + 1, acc + n , to) + counter(rest, n + 1, acc, to)
 
while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(counter(n, 0, 0, s))
### BUGGY CODE ###

"""
01BFS: ステップ数が多ければ後ろに持っていく
"""
from collections import deque
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = [list(input()) for _ in range(H)]

que = deque([(Ch-1,Cw-1,0)])
adjectns = [(1,0),(0,1),(-1,0),(0,-1)]
while que:
    h,w,step = que.popleft()
    if h == Dh-1 and w == Dw-1:
        print(step)
        exit()
    else:
        if maze[h][w] == ".":
            maze[h][w] = step
            for a,b in adjectns:
                x = h + a
                y = w + b
                if 0<=x<H and 0<=y<W:
                    que.appendleft((x,y,step))
            for i in range(-2,3):
                for j in range(-2,3):
                    x = h+i
                    y = w+j
                    if 0<=x<H and 0<=y<W:
                        que.append((x,y,step+1))
print(-1)



### FIXED CODE ###

"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


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

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    nxQue = deque([])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    INF = 10**13
    for _ in range(INF):
        if not que:
            if nxQue:
                que = nxQue
                nxQue = deque([])
                continue
            else:
                break
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    if b == 0:
                        for i in range(a,a*3,a):
                            for j in range(-2,3,1):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
                    else:
                        for i in range(-2,3,1):
                            for j in range(b,b*3,b):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()