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

N, Q = map(int, input().split())
S = input()
s = S[:2]
ans = 'AC'
lst = []
for i in range(N-1):
    s = S[i] + S[i + 1]
    lst.append(s == ans)

for _ in range(Q):
    a, b = map(int, input().split())
    res = 0
    for i in range(a - 1, b - 1):
        res += lst[i]
    print(res)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
s = S[:2]
ans = 'AC'
lst = [0]
count = 0
for i in range(N-1):
    s = S[i] + S[i + 1]
    count += (s == ans)
    lst.append(count)

for _ in range(Q):
    a, b = map(int, input().split())
    print(lst[b - 1] - lst[a - 1])
### BUGGY CODE ###

def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

  for i in range(N):
      d[i][i] = 0

  for i in range(M):
      a, b, c = map(int, input().split())
      a -= 1
      b -= 1
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


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


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      ans = min(ans, temp)

  print(ans)
hoge()


### FIXED CODE ###

from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()
### BUGGY CODE ###

N = int(input())

d = {}
ans = []

for i in range(N):
    S = input()
    d.setdefault(S,0)
    d[S] += 1

for key in d.keys():
    if d[key] == max(d.values()):
        ans.append(key)
        
ans = sorted(ans)

for word in ans:
    print(word)

### FIXED CODE ###

N = int(input())

d = {}
ans = []

for i in range(N):
    S = input()
    d.setdefault(S,0)
    d[S] += 1

max = max(d.values())
for key in d.keys():
    if d[key] == max:
        ans.append(key)
        
ans = sorted(ans)

for word in ans:
    print(word)
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Edge2 = defaultdict(lambda: [])

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Edge2[B-1].append(A-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if len(Edge2[en]) == 1:
                Q.append(en)
            else:
                Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)    


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)
### BUGGY CODE ###

import itertools

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

circle = list(itertools.combinations(L, 3))

count = 0
for c in circle:
    if c[0] < c[1] + c[2] and c[1] < c[2] + c[0] and c[2] < c[0] + c[1]:
        count += 1

print(count)

### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()

count = 0
for i in range(n):
    for j in range(i + 1, n):
        count += (bisect.bisect_left(L, L[i] + L[j]) - j - 1)

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

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

for i in range(n):
    if 1 < l.count(l[i]):
        p = "NO"
        break
    
print(p)

### FIXED CODE ###

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

if len(l) != len(set(l)):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

#coding:utf-8                                                                                         
import random

def is_prime(q,k=20):
    #計算するまでもなく判定できるものははじく                                                         
    if q < 2: return False # 2未満に素数はない                                                        
    if q == 2 or q == 3 or q == 5: return True # 2,3,5は素数                                          
    if q % 2 == 0 or q % 3 == 0 or q % 5 == 0: return False # 2,3,5の倍数は合成数                     

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める                                                  
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    #判定をk回繰り返す                                                                                
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック                                                                
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True


Q = int(raw_input())
LR = []
for i in range(Q):
    l, r = map(int, raw_input().split())
    LR.append((l, r))

for l, r in LR:
    count = 0
    for j in range(l, r+1, 2):
        if is_prime(j):
            if is_prime((j+1)/2):
                count += 1
    print count

### FIXED CODE ###

import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data

primes = set(get_sieve_of_eratosthenes(10**5))
A = []
for i in range(1, 10**5+1):
  if i % 2 == 1:
    if i in primes and (i+1) // 2 in primes:
      A.append(1)
    else:
      A.append(0)
  else:
    A.append(0)

for i in range(1, len(A)):
  A[i] += A[i-1]

q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  if l == 1:
    l = 2
  ans = A[r-1] - A[l-2]
  print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
C = list(map(int, input().split()))

I = [[] for _ in range(N)] #各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [0 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c+1 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [[list(map(lambda a: int(a)-1, input().split())), i] for i in range(Q)] #クエリ
S.sort(key = lambda a: a[0][1]) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  while S and S[-1][0][1] == j:#クエリへの返答
    s = S.pop()
    ans[s[1]] = BIT_query(s[0][1]+1) - BIT_query(s[0][0])
  
  if not S:
    break
    
  if loc[j] > 0: #最右端の玉である場合
    c = loc[j]-1
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c+1
       
for a in ans:
  print(a)


### FIXED CODE ###

from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')
### BUGGY CODE ###

N= int(input())
Alist = list(map(int, input().split())) 
res = 1
if N % 2 ==0:
    for i in range(0,N//2):
        res = res*2 % (10**9+7)
        if Alist.count(2*i+1) != 2:
            print(0)
            exit()

    print(res)

else:
    if Alist.count(0) != 1:
        print(0)
        exit()
    else:
        for i in range(1,(N+1)//2):
            res = res*2 % (10**9+7)
            if Alist.count(2*i) != 2:
                print(0)
                exit()
    print(res)

### FIXED CODE ###

from collections import Counter

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

count = Counter(Alist)
res = 1
if N % 2 ==0:
    for i in range(1,N,2):
        if count[i] != 2:
            print(0)
            exit()
else:
    if count[0] != 1:
        print(0)
        exit()
    else:
        for i in range(2,N,2):
            if count[i] != 2:
                print(0)
                exit()
print(2**(N//2) % (10**9+7))
### BUGGY CODE ###

s = str(input())
l = []
x = []
for i in range(len(s)):
    for j in range(len(s)-1,0,-1):
        if s[i] == "A":
            l.append(i)
            if s[j] == "Z":
                x.append(j)
print(max(x)-min(l)+1)

### FIXED CODE ###

s = str(input())
a = []
b = []
for i in range(len(s)):
    if s[i] == "A":
        a.append(i)
    elif s[i] == "Z":
        b.append(i)
print(max(b)-min(a)+1)
### BUGGY CODE ###

# @author 

import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
        for k in range(n + 1):
            for j in range(n + 1):
                for i in range(n + 1 - j - k):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
        for k in range(n + 1):
            for j in range(n + 1 - k):
                for i in range(n + 1 - j - k):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

N = int(input())
A = [[]] + [list(map(int, input().split())) for n in range(N)]
P = [0] * (N + 1)

def get_num(i):
    if P[i] >= N - 1:
        return -1
    return A[i][P[i]]


def update(mem):
    for i in mem:
        P[i] += 1


def f():
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if P.count(N - 1) == N:
            return t

        for i in range(1, N + 1):
            if i in mem:
                continue

            j = get_num(i)
            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1

        update(mem)
        mem = set()

    return -2

print(f())


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for n in range(N)]
P = [0] * N


def get_num(i):
    return A[i][P[i]] - 1


def update(mem, K):
    for i in mem:
        P[i] += 1
        if P[i] == N - 1:
            K.remove(i)


def f():
    K = {i for i in range(N)}
    L = {i for i in range(N)}
    mem = set()
    for t in range(N * (N - 1) // 2 + 1):
        if len(K) == 0:
            return t

        for i in L:
            if i in mem:
                continue

            j = get_num(i)
            if j in mem:
                continue

            if i == get_num(j):
                mem.add(i)
                mem.add(j)

        if len(mem) == 0:
            return -1
        update(mem, K)
        L = K & mem
        mem.clear()

    return -2

print(f())
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
def has_duplicates2(seq):
    seen = []
    unique_list = [x for x in seq if x not in seen and not seen.append(x)]
    return len(seq) != len(unique_list)
print("NO" if has_duplicates2(a) else "YES")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set(a)
a.sort()
if len(a) != len(b):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

WV = []

N, W = [int(v) for v in input().strip().split(' ')]

for _ in range(N):
    WV.append([int(v) for v in input().strip().split(' ')])

def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memoize
def find(w, l):   # あとw持てるときの最大価値（lはすでにナップサックに入っているもの）
    mx = 0
    for i in range(N):
        if w - WV[i][0] < 0 or l & (1 << i):
            continue
        mx = max(mx, WV[i][1] + find(w - WV[i][0], l + 1 << i))
    return mx

print(find(W, 0))


### FIXED CODE ###

import numpy as np
import sys

N, W = [int(v) for v in input().strip().split(' ')]
dp = np.zeros(W + 1, dtype = 'uint64')

for _ in range(N):
    w, v = [int(v) for v in sys.stdin.readline().split(' ')]
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])

print(dp[W])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
p=[0]*(10**6+1)
for i in range(n):
    if p[a[i]]==0:
        j=2
        while a[i]*j<=10**6:
            p[a[i]*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
m=len(b)

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
X = []
for i in range(N):
    X.append(list(map(int, input().split())))
X.sort(key=lambda x: (-x[1], x[0]))

days = [i for i in range(1, M+1)]
ans = 0
for a, b in X:
    if len(days) == 0:
        break
    if days[-1] < a:
        continue
    index = bisect.bisect_right(days, a)
    if index > 0 and days[index-1] >= a:
        days.pop(index-1)
    elif index > 0 and days[index-1] <a:
        days.pop(index) 
    elif index == 0 and days[0] >= a:
        days.pop(0)
    else:
        continue
    ans += b
print(ans)

### FIXED CODE ###

import bisect
import heapq
N, M = map(int, input().split())
X = [[] for _ in range(M)]
for i in range(N):
    a, b = map(int, input().split())
    if a <= M:
        X[a-1].append(-b)
ans = 0
heap = []
for i in range(M):
    for b in X[i]:
        heapq.heappush(heap, b)
    if len(heap) > 0:
        ans -= heapq.heappop(heap)
print(ans)

def TLE():
    X.sort(key=lambda x: (-x[1], x[0]))
    days = [i for i in range(1, M+1)]
    ans = 0
    for a, b in X:
        if len(days) == 0:
            break
        if days[-1] < a:
            continue
        index = bisect.bisect_right(days, a)
        if index > 0 and days[index-1] >= a:
            days.pop(index-1)
        elif index > 0 and days[index-1] <a:
            days.pop(index) 
        elif index == 0 and days[0] >= a:
            days.pop(0)
        else:
            continue
        ans += b
    print(ans)
# TLE()
### BUGGY CODE ###

import sys

def main():
    S = list(input())
    a = []
    for i in range(0, len(S) + 1):
        a.append(0)
    
    while True:
        change_count = 0
        for i in range(0, len(S)):
            if S[i] == '<' and a[i] >= a[i + 1]:
                a[i + 1] = a[i] + 1
                change_count += 1
            elif S[i] == '>' and a[i] <= a[i + 1]:
                a[i] += 1
                change_count += 1
        if change_count == 0:
            total = 0
            for i in range(0, len(a)):
                total += a[i]
            print(total)
            sys.exit()

main()


### FIXED CODE ###

def main():
    S = list(input())
    N = len(S) + 1
    a = [-1] * N
    for i in range(N):
        if a[i] == -1:
            calc(i, S, a)

    print(sum(a))

def calc(i, S, a):
    if i == 0:
        if S[i] == '<':
            a[i] = 0
        else:
            j = 0
            while j < len(S) and S[j] == '>':
                j += 1
            for k in range(j):
                a[k] = j - k
    elif i == len(S):
        if S[i - 1] == '>':
            a[i] = 0
        else:
            a[i] = a[i - 1] + 1
    else:
        if S[i - 1] == '<' and S[i] == '<':
            a[i] = a[i - 1] + 1
        elif S[i - 1] == '<' and S[i] == '>':
            j = 0
            while (i + j) < len(S) and S[i + j] == '>':
                j += 1
            for l in range(j):
                a[i + l] = j - l
            a[i] = max(a[i - 1] + 1, j)
        elif S[i - 1] == '>' and S[i] == '<':
            a[i] = 0
        elif S[i - 1] == '>' and S[i] == '>':
            a[i] = a[i - 1] - 1

main()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.append((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.appendleft((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.appendleft((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()