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

# 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

import sys


def main():
    N = int(input())  # 桁数
    S = str(input())
    
    ans = set()
    
    for i in range(0, N - 2):
        for j in range(i + 1, N - 1):
            for k in range(j + 1, N):
                code = S[i] + S[j] + S[k]
                ans.add(code)
    
    print(len(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

import sys


def main():
    N = int(input())  # 桁数
    S = str(input())

    ans = set()

    digit1 = set()

    for i in range(0, N - 2):
        if S[i] in digit1:
            continue
        digit1.add(S[i])
        digit2 = set()

        for j in range(i + 1, N - 1):
            if S[j] in digit2:
                continue
            digit2.add(S[j])
            digit3 = set()
            for k in range(j + 1, N):
                if len(digit3) == 10:
                    break
                code = S[i] + S[j] + S[k]
                ans.add(code)

    print(len(ans))


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

from bisect import bisect_left, bisect_right

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

answer = 0
for b in B:
    ai = bisect_left(A, b)
    ci = bisect_right(C, b)
    answer += len(A[:ai]) * len(C[ci:])
print(answer)


### FIXED CODE ###

import bisect

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

answer = 0
for b in B:
    ai = bisect.bisect_left(A, b)
    ci = bisect.bisect_right(C, b)
    answer += ai * (N - ci)

print(answer)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().strip()
n,a,b=map(int,input().split())
mod=10**9+7
def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod)%mod
print(((2**n)-1-fur(n,a)-fur(n,b))%mod)



### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def f(k,l):
    ans=1
    for i in range(1,l+1):ans=(ans*(k-i+1)*pow(i,mod-2,mod))%mod
    return ans
print((pow(2,n,mod)-1-f(n,a)-f(n,b))%mod)
### BUGGY CODE ###

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
    c = (l+r)//2
    x = 0
    for a in A:
      if a >= 0:
        ll = -1
        rr = N
        while(ll+1 < rr):
          cc = (ll+rr)//2
          if a*A[cc] < c:
            ll = cc
          else:
            rr = cc
        x += ll+1
      else:
        ll = -1
        rr = N
        while (ll+1 < rr):
          cc = (ll+rr)//2
          if a*A[cc] < c:
            rr = cc
          else:
            ll = cc
        x += N-rr
      if a*a < c:
        x -=1
    x //= 2
    if x < K:
      l = c
    else:
      r = c
  print(l)

if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  N,K = map(int,input().split())
  A = sorted(list(map(int,input().split())))
  
  AM = []
  AP = []
  for a in A:
    if a > 0:
      AP.append(a)
    elif a < 0:
      AM.append(a)

  INF = 10**18+1
  l = -INF
  r = INF
  while(l+1 < r):
    # 積がc未満となるペアの個数xを求める。
    # K番目の積は、それより小さい積の個数がK未満である席のうち最大のもの。
    c = (l+r)//2
    x = 0
    if c > 0:
      i = len(AP)-1
      for j in range(len(AP)):
        if j >= i:
          break
        while(j < i and AP[i]*AP[j] >= c):
          i -= 1
        x += i-j
      i = 0
      for j in range(len(AM)-1,-1,-1):
        if j <= i:
          break
        while (i < j and AM[i]*AM[j] >= c):
          i += 1
        x += j-i
      #print(c,x)
      x += len(AP)*len(AM)
      x += (len(AP)+len(AM))*(N-len(AP)-len(AM))
      if N-len(AP)-len(AM) > 1:
        x += (N-len(AP)-len(AM))*(N-len(AP)-len(AM)-1)//2
    elif c == 0:
      x += len(AP)*len(AM)
    else:
      i = 0
      for j in range(len(AM)):
        while(i < len(AP) and AP[i]*AM[j] >= c):
          i += 1
        x += len(AP)-i

    #print(l,r,c,x)
    if x < K:
      l = c
    else:
      r = c
  print(l)

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

n=int(input())
a=list(input().split())
b=[]
for i in range(n):
    b.append(a[i])
    b.reverse()
print(' '.join(b))


### FIXED CODE ###

n=int(input())
a=list(input().split())
b=a[::-2]+a[len(a)%2::2]
print(' '.join(b))
### BUGGY CODE ###

N, M = map(int, input().split())
#E = [sorted(list(map(int, input().split()))) for i in range(M)]
V = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    V[A].append(B)
    V[B].append(A)

L = [-1]*(N+1)
L[1] = 0
al = False

from collections import deque
Open = deque()
Open.append(1)
Close = set()
while len(Open)>0:
    v = Open.pop()
    Close.add(v)
    for v2 in V[v]:
        if v2 not in Close:
            Open.append(v2)
        if L[v2] == -1:
            L[v2] = 1-L[v]
        elif L[v] + L[v2] != 1:
            al = True
            break
    if al:
        break

#print(V, L, al)
if al:
    print(N*(N-1)//2-M)
else:
    c = L.count(1)
    print(c*(N-c)-M)



### FIXED CODE ###

N, M = map(int, input().split())
V = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    V[A].append(B)
    V[B].append(A)

L = [-1]*(N+1)
L[1] = 0
al = False

from collections import deque
Open = deque()
Open.append(1)
Close = set()
while len(Open)>0:
    v = Open.pop()
    Close.add(v)
    for v2 in V[v]:
        if v2 not in Close:
            Open.append(v2)
        if L[v2] == -1:
            L[v2] = 1-L[v]
        elif L[v] + L[v2] != 1:
            al = True
            break
    if al:
        break

if al:
    print(N*(N-1)//2-M)
else:
    c = L.count(1)
    print(c*(N-c)-M)
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    cnt = 0

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)



### FIXED CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    cnt = 0

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i, P)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
num = list(map(int, input().split()))
ans = 0
for i in range(n):
    if i == 0:
        ans = num[0]
    else:
        ans*=num[i]

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

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
num = list(map(int, input().split()))
ans = 0
flg = 0
for i in range(n):
    if num[i] == 0:
        flg = 1;
        break
    
for i in range(n):
    if flg == 1:
        print(0)
        break
    elif i == 0:
        ans = num[0]
    else:
        ans*=num[i]
    
    if ans > 10 ** 18 and flg ==0:
        print(-1)
        break
    

if ans <= 10 ** 18 and flg == 0:
    print(ans)
### BUGGY CODE ###

import sys
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
finished = 0
for i in range(n):
  if a[i] == b[i]:
    finished += 1
while True:
  maxn = -1
  maxi = -1
  for i in range(n):
    if a[i] == b[i]:
      continue
    if maxn < b[i]:
      maxn = b[i]
      maxi = i
  if maxi == 0:
    b[maxi] -= b[n - 1] + b[1]
  elif maxi == n - 1:
    b[maxi] -= b[n - 2] + b[0]
  else:
    b[maxi] -= b[maxi - 1] + b[maxi + 1]
  result += 1
  if a[maxi] == b[maxi]:
    finished += 1
  if finished == n:
    print(result)
    sys.exit()
  if a[maxi] > b[maxi]:
    print(-1)
    sys.exit()


### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

h,w = map(int,input().split())

s = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]

for i in range(h):
    done=[0] * w

    for j in range(w):
        if s[i][j] == '#': continue
        if done[j] :continue

        l = 0
        while j+l < w:
            if s[i][j+l] == '#': break
            l+=1

        for k in range(l):
            cnt[i][j+k] +=l
            done[j+k] = 1

for j in range(w):
    done=[0] * h

    for i in range(h):
        if s[i][j] == '#': continue
        if done[i] :continue

        l = 0
        while i+l < h:
            if s[i+l][j] == '#': break
            l+=1

        for k in range(l):
            cnt[i+k][j] +=l
            done[i+k] = 1

ans=0

for i in range(h):
    for j in range(w):
        ans = max(ans,cnt[i][j]-1)

print(ans)

### FIXED CODE ###

h,w = map(int,input().split())

s = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]

for i in range(h):
    done=[0] * w

    for j in range(w):
        if s[i][j] == '#': continue
        if done[j] :continue

        l = 0
        while j+l < w:
            if s[i][j+l] == '#': break
            l+=1

        for k in range(l):
            cnt[i][j+k] +=l
            done[j+k] = 1

for j in range(w):
    done=[0] * h

    for i in range(h):
        if s[i][j] == '#': continue
        if done[i] :continue

        l = 0
        while i+l < h:
            if s[i+l][j] == '#': break
            l+=1

        for k in range(l):
            cnt[i+k][j] +=l
            done[i+k] = 1

ans=0

for i in range(h):
    for j in range(w):
        ans = max(ans,cnt[i][j]-1)

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

import functools
import operator

#A,B,C=(int(x) for x in input().split())
N=int(input())
A=list(map(int, input().split()))

result = functools.reduce(operator.mul, A)

if result<=10**18:
  print(result)
else:
  print(-1)

### FIXED CODE ###

#A,B,C=(int(x) for x in input().split())
N=int(input())
A=list(map(int, input().split()))


if 0 in A:
  t=0
else:
  t=A[0]
  i=1
  for k in range(N-1):
    t=t*A[i]
    if t>10**18:
      break
    i+=1

if t<=10**18:
  print(t)
else:
  print(-1)
### BUGGY CODE ###

s = list(input())
len_s = len(s)
list_s = []
for i in range(1, len_s + 1):
    for j in range(len_s):
        if j + i <= len_s:
            list_s.append(''.join(s[j:j + i]))
ans = 0
for i in range(1, 101):
    seq = str(2019 * i)
    ans += list_s.count(seq)
print(ans)


### FIXED CODE ###

from collections import Counter
s = input()[::-1]
cnt = [0]
d = 0
mod = 2019

for i in s:
    tmp = int(i) * pow(10, d, mod) % mod
    tmp = cnt[-1] + tmp
    cnt.append(tmp % mod)
    d += 1

cnt = Counter(cnt)
ans = sum(j * (j - 1) // 2 for j in cnt.values())
print(ans)
### BUGGY CODE ###

N=int(input())
a=1
for b in range(a,N+1):
    a*=b
print(a%(10**9+7))


### FIXED CODE ###

N=int(input())
a=1
for b in range(a,N+1):
    a*=b
    if a>10**9+7:
        a=a%(10**9+7)
print(a)
### BUGGY CODE ###

N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
for l in ls2:
    lsn = [l[1] if i == l[0] else i for i in lsn]
    print(sum(lsn))

### FIXED CODE ###

import collections
N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = collections.Counter(lsn)
sum1 = sum(lsn)
for l in ls2:
    sum1 = sum1 +(l[1]-l[0])*index[l[0]]
    index[l[1]] += index[l[0]]
    index[l[0]] = 0
    print(sum1)
### BUGGY CODE ###

N = int(input())

i =1
j =0
while j <N:
    i=i*(j+1)
    j+=1
print(i%(10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

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

INF = 10**5
dp = [[INF] * (1 << n) for i in range(n)]
for i in range(n):
    dp[i][1 << i] = i

for bit_state in range(1 << n):
    cnt1 = bin(bit_state).count("1")
    for i in range(n):
        cnt0 = -1
        if not(bit_state & (1 << i)):
            continue
        for j in range(n):
            if bit_state & (1 << j):
                continue
            cnt0 += 1
            num_i = a[i] if (cnt1 - 1) % 2 == i % 2 else b[i]
            num_j = a[j] if (cnt1) % 2 == j % 2 else b[j]
            if num_i <= num_j:
                dp[j][bit_state | (1 << j)] = min(dp[j][bit_state | (1 << j)], dp[i][bit_state] + cnt0)

ans = 10**5
for i in range(n):
    ans = min(ans, dp[i][-1]) 
if ans == 10**5:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


from operator import itemgetter
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 10**18


for bit_state in range(1 << n):
    pattern = [[] for i in range(2)]
    for i in range(n):
        if bit_state & (1 << i) and i % 2 == 0:
            pattern[0].append(a[i]*100 + i)
        elif bit_state & (1 << i) and i % 2 == 1:
            pattern[1].append(a[i]*100 + i)
        elif i % 2 == 0:
            pattern[1].append(b[i]*100 + i)
        else:
            pattern[0].append(b[i]*100 + i)

    if len(pattern[0]) == len(pattern[1]) or len(pattern[0]) - 1 == len(pattern[1]):
        for i in range(2):
            pattern[i] = sorted(pattern[i])
        bit = BIT(n)
        ans_tmp = 0
        prev_num = 10**8
        for i in range(n)[::-1]:
            pal = i % 2
            num = pattern[pal].pop()
            ind = num % 100
            num = num // 100
            if prev_num < num:
                break
            prev_num = num
            bit.add(ind, 1)
            ans_tmp += bit.get_sum(0, ind)
        else:
            ans = min(ans, ans_tmp)

if ans == 10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

x = N
while x > abs(x-K):
    x = abs(x-K)

print(x)


### FIXED CODE ###



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

A = N % K

print(min(A, abs(A - K)))
### BUGGY CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for _ in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = accumulate(temp)
        if templi == dists:
            break
        else:
            dists = templi
    for _ in range(number):
        print(next(dists))


if __name__ == '__main__':
    main()

# Pypy 3 なら通る。Python 3 では無理。


### FIXED CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


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

from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def gcd2(a, b):
  while b != 0:
    a, b = b, a % b
  return a

def gcd(a, b, c):
  return gcd2(gcd2(a, b), c)

res = 0

for i in range(1, N + 1):
  for j in range(1, N + 1):
    for k in range(1, N + 1):
      res += gcd(i, j, k)

print(res)


### FIXED CODE ###

from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def gcd2(a, b):
  while b != 0:
    a, b = b, a % b
  return a

def gcd(a, b, c):
  return gcd2(gcd2(a, b), c)

res = 0

for i in range(1, N + 1):
  for j in range(i, N + 1):
    for k in range(j, N + 1):
      if i == j == k:
        res += gcd(k, j, i)
      elif i != j != k:
        res += gcd(k, j, i) * 6
      else:
        res += gcd(k, j, i) * 3

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

import sys

def L(l,i,last):
    l[i-1] += last[i]
    l[i] -= last[i]
    last[i] = l[i]
    last[i-1] = l[i-1]

def R(l,i,last):
    l[i+1] += last[i]
    l[i] -= last[i]
    last[i] = l[i]


def main():
    S = input()

    maxLR = 0
    tmpLR = 0
    last = ''
    funcS = []
    for s in S:
        if s == last:
            tmpLR += 1
        else:
            maxLR = max(maxLR, tmpLR)
            tmpLR = 1
            last = s

        if s == 'R':
            funcS.append(R)
        else:
            funcS.append(L)
    
    maxLR = max(maxLR, tmpLR)
    
    loop = maxLR if maxLR % 2 == 0 else maxLR -1
    
    lenS = len(S)
    ch = [1]*lenS
    lastch = [1]*lenS
    for i in range(loop):
        for j in range(lenS):
            if ch[j] == 0:
                continue
            funcS[j](ch,j,lastch)
            # print(i,j, ch)

    print(*ch)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
import math

def main():
    S = input()
    lenS = len(S)
    ch = [0]*lenS

    tmpLR = 0
    last = ''
    for i, s in enumerate(S):
        if s == last:
            tmpLR += 1
        else:
            if last == 'R':
                ch[i-1] = tmpLR
            elif last == 'L':
                ch[i-tmpLR] = tmpLR

            tmpLR = 1
            last = s
    
    ch[-tmpLR] = tmpLR

    for i,c in enumerate(ch):
        if c == 0 or S[i] == 'L':
            continue
        if S[i] == 'R':
            rch = c
            lch = ch[i+1]
            rleft = math.ceil(rch/2)
            lleft = math.ceil(lch/2)
            ch[i] = rleft + lch - lleft
            ch[i+1] = lleft + rch - rleft

    print(*ch)

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

N = int(input())
S = input()
S = S.replace('W', '1')
S = S.replace('E', '0')
S = list(map(int, list(S)))
ans = min([ sum(S[:i]) + len(S[i+1:]) - sum(S[i+1:]) for i in range(N) ])
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = S.count('E')
w = 0
e = S.count('E')
for i in range(N):
    if S[i-1] == 'W' and i != 0:
        w += 1
    if S[i] == 'E':
        e -= 1
    if w + e < ans:
        ans = w + e
print(ans)
### BUGGY CODE ###

from collections import Counter
int = int(input())
word = [input() for i in range(int)]
s = Counter(word)
u = [k for k, v in s.items() if v == max(s.values())]
u.sort()
for j in range(len(u)):
    print(u[j])

### FIXED CODE ###

from collections import Counter
int = int(input())
word = [input() for i in range(int)]
s = Counter(word).most_common()
u = s[0][1]
v = []
for i, j in s:
  if j == u:
    v.append(i)
v.sort()
print(*v)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 0

for x in range(a+1):
  for y in range(a+1):
    for z in range(a+1):
      if x + y + z == b:
        ans += 1

print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 0

for x in range(a+1):
  for y in range(a+1):
    z = b - x - y
    
    if z >= 0 and a >= z:
      ans += 1

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

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

tmp = 0
sum_a = sum(A)
ind = N+1
for i in range(N-1):
    #tmp += A[i]*2
    tmp = 2*sum(A[:i+1])
    if tmp < A[i+1]:
        ind = i

if ind == N+1:
    print(N)
else:
    print(N-ind-1)

### FIXED CODE ###

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

tmp = 0
sum_a = sum(A)
ind = N+1
for i in range(N-1):
    tmp += A[i]*2
    if tmp < A[i+1]:
        ind = i

if ind == N+1:
    print(N)
else:
    print(N-ind-1)
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())

array_st=list(map(int,input().split()))
array_gl=list(map(int,input().split()))
start_point=[]
goal_point=[]
for i in range(2):
    start_point.append(array_st[i]-1)
    goal_point.append(array_gl[i]-1)

matrix=[]
for i in range(H):
    matrix.append(list(input()))

d=deque()
d.append([start_point[0],start_point[1],0])

road=[-1,1]

ans=-1
while d:
    v=d.popleft()
    matrix[v[0]][v[1]]="x"
    if [v[0],v[1]]==goal_point:
        ans=v[2]
        break
    for i in road:
        if v[0]+i>=0 and v[0]+i<H:
            if matrix[v[0]+i][v[1]]==".":
                d.appendleft([v[0]+i,v[1],v[2]])
        if v[1]+i>=0 and v[1]+i<W:
            if matrix[v[0]][v[1]+i]==".":
                d.appendleft([v[0],v[1]+i,v[2]])

    for i in range(-2,3):
        for j in range(-2,3):
            if v[0]+i>=0 and v[0]+i<H:
                if v[1]+j>=0 and v[1]+j<W:
                    if matrix[v[0]+i][v[1]+j]==".":
                        d.append([v[0]+i,v[1]+j,v[2]+1])

print(ans)

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())

array_st=list(map(int,input().split()))
array_gl=list(map(int,input().split()))
start_point=[]
goal_point=[]
for i in range(2):
    start_point.append(array_st[i]-1)
    goal_point.append(array_gl[i]-1)

matrix=[]
for i in range(H):
    matrix.append(list(input()))

d=deque()
d.append([start_point[0],start_point[1],0])

road=[-1,1]

ans=-1
while d:
    v=d.popleft()
    if matrix[v[0]][v[1]]=="x":
        continue
    matrix[v[0]][v[1]]="x"
    if [v[0],v[1]]==goal_point:
        ans=v[2]
        break
    for i in road:
        if v[0]+i>=0 and v[0]+i<H:
            if matrix[v[0]+i][v[1]]==".":
                d.appendleft([v[0]+i,v[1],v[2]])
        if v[1]+i>=0 and v[1]+i<W:
            if matrix[v[0]][v[1]+i]==".":
                d.appendleft([v[0],v[1]+i,v[2]])

    for i in range(-2,3):
        for j in range(-2,3):
            if v[0]+i>=0 and v[0]+i<H:
                if v[1]+j>=0 and v[1]+j<W:
                    if matrix[v[0]+i][v[1]+j]==".":
                        d.append([v[0]+i,v[1]+j,v[2]+1])

print(ans)