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

import math
n = int(input())
s = int(input())

def f(b, n):
    ans = 0
    while b <= n:
        ans += n%b
        n //= b
    ans += n
    return ans

if n == s:
    print(n+1)
else:
    for b in range(2, math.ceil(math.sqrt(n)) + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(math.ceil(math.sqrt(n)), 0 ,-1):
            if s - p >= 0 and n-s+p > 0:
                b = round((n-s+p)/p, )
                if f(b, n) == s:
                    print(b)
                    break
        else:
            print(-1)

### FIXED CODE ###

import math
n = int(input())
s = int(input())

def f(b, n):
    ans = 0
    while b <= n:
        ans += n%b
        n //= b
    ans += n
    return ans

if n == s:
    print(n+1)
elif n < s:
    print(-1)
else:
    limit = math.ceil(math.sqrt(n))
    for b in range(2, limit + 1):
        if f(b, n) == s:
            print(b)
            break
    else:
        for p in range(limit, 0 ,-1):
            if s - p >= 0 and n-s+p > 0 and (n-s+p)//p > limit:
                b = (n-s+p)//p
                if f(b, n) == s:
                    print(b)
                    break
        else:
            print(-1)
### BUGGY CODE ###

from itertools import accumulate

k, q = map(int, input().split())
d = list(map(int, input().split()))

def sof(n, a, b, c):
    if a == 0:
        return (n + 1) * (b // c)
    if a >= c or b >= c:
        return n * (n + 1) // 2 * (a // c) + (n + 1) * (b // c) + sof(n, a % c, b % c, c)
    m = (a * n + b) // c
    return n * m - sof(m - 1, c, c - b - 1, a)

def solve():
    n, x, m = map(int, input().split())
    a = [0] + list(map(lambda i: i % m, accumulate(d)))
    ans = 0
    rn = (n - 1) % k
    for i in range(k):
        u = (x + a[i]) % m
        v = (x + a[i + 1]) % m
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        if u == v:
            continue
        elif u < v:
            ans += c - (sof(c - 1, a[-1], v, m) - sof(c - 1, a[-1], u, m))
        else:
            ans += sof(c - 1, a[-1], u, m) - sof(c - 1, a[-1], v, m)
    print(ans)

for _ in range(q):
    solve()

### FIXED CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    f = x % m
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        ans += c
        f += c * (d[i] % m)
    ans -= f // m
    print(ans)

for _ in range(q):
    solve()
### BUGGY CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

D1 = T1 * A1 - T1 * B1
D2 = T1 * A1 + T2 * A2 - T1 * B1 - T2 * B2

if D1 * D2 > 0:
    print(0)
elif D2 == 0:
    print("infinity")
else:
    c = 1
    D1 = abs(D2 - D1)
    D2 = abs(D2)
    Dp = D2
    while True:
        Dp += D2
        if Dp > D1:
            break
        elif Dp == D1:
            c += 1
            break
        c += 2
    print(c)

### FIXED CODE ###

T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

D1 = T1 * A1 - T1 * B1
D2 = T1 * A1 + T2 * A2 - T1 * B1 - T2 * B2

if D1 * D2 > 0:
    print(0)
elif D2 == 0:
    print("infinity")
else:
    D1 = abs(D2 - D1)
    D2 = abs(D2)
    c = (D1 // D2) * 2 - 1
    if D1 % D2 == 0:
        c -= 1
    print(c)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans % 1000000007)

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

import math

def cal(sum_, F, N, K, d):
    count = 0
    for i in range(N):
        if sum_[i] > d:
            count += math.ceil((sum_[i] - d) / F[i])
            if count > K:
                #作ることができない
                return False
    return True


def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    F = [int(i) for i in input().split()]
    A.sort()
    F.sort(reverse=True)
    sum_ = []
    for i in range(N):
        sum_.append(A[i] * F[i])

    right = 10 ** 12
    left = 0
    count = 0
    pre_mid = 0
    while count < 100:
        mid = (right + left) // 2
        if pre_mid == mid:
            break
        if cal(sum_, F, N, K, mid):
            # midを小さくすることができる
            right = mid
        else:
            # midを大きくしなければならない
            left = mid + 1
        pre_mid = mid
        count += 1
    print(mid)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math

def cal(sum_, F, N, K, d):
    count = 0
    for i in range(N):
        if sum_[i] > d:
            count += math.ceil((sum_[i] - d) / F[i])
            if count > K:
                #作ることができない
                return False
    return True


def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    F = [int(i) for i in input().split()]
    A.sort()
    F.sort(reverse=True)
    sum_ = []
    for i in range(N):
        sum_.append(A[i] * F[i])

    right = 10 ** 12
    left = 0
    count = 0
    pre_mid = 0
    while True:
        mid = (right + left) // 2
        if pre_mid == mid:
            break
        if cal(sum_, F, N, K, mid):
            # midを小さくすることができる
            right = mid
        else:
            # midを大きくしなければならない
            left = mid + 1
        pre_mid = mid
        count += 1
    print(mid)


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

import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, m = na()
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = na()
    x -= 1; y -= 1
    g[x].append(y)

def dfs(v):
    dist = [-1] * n
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in g[v]:
            dist[w] = dw
            stack.append(w)
    return max(dist)

print(max(dfs(x) for x in range(n)))



### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**7)

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, m = na()
memo = [-1] * n
def dp(v):
    if memo[v] != -1:
        return memo[v]
    if G[v]:
        memo[v] = max(dp(i) for i in G[v]) + 1
    else:
        memo[v] = 0
    return memo[v]


G = [[] for _ in range(n)]
for _ in range(m):
    f, t = na()
    G[f-1].append(t-1)
print(max([dp(i) for i in range(n)]))
### BUGGY CODE ###


from bisect import bisect_right

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

d = {"R": [], "G": [], "B": []}
for i in range(N):
    d[S[i]].append(i)

ctr = {k: len(v) for k, v in d.items()}
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            c = (set("RGB") - set([S[i], S[j]])).pop()
            cnt = ctr[c] - bisect_right(d[c], j)

            k = 2 * (j + 1) - (i + 1) - 1
            if j < k < N and c == S[k]:
                cnt -= 1

            ans += max(0, cnt)

print(ans)


### FIXED CODE ###

from bisect import bisect_right

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

d = [[0] * N for _ in range(3)]
for i in range(3):
    for j in range(N):
        d[i][j] = int(S[j] == "RGB"[i])
        
cumsum = [[0] * (N + 1) for _ in range(3)]
for i in range(3):
    for j in range(N):
        cumsum[i][j + 1] = cumsum[i][j] + d[i][j]

cnt = [len(v) for v in d]
ans = 0
for i in range(1, N - 1):
    for j in range(i + 1, N):
        
        if S[i - 1] == S[j - 1]:
            continue

        # Find `k` string and index
        s = (set("RGB") - set([S[i - 1], S[j - 1]])).pop()
        idx = "RGB".find(s)
        ans += cumsum[idx][-1] - cumsum[idx][j]
        
        k = 2 * j - i
        if k <= N and d[idx][k - 1]:
            ans -= 1
        
print(ans)
### BUGGY CODE ###

import itertools
N = int(input())
ans = 0
for a in range(2,N - 1):
    for b in range(2,N - 1):
        if a * b < N:
            ans += 1
        elif a * b >= N:
            break
print(ans + ((N - 1) * 2 - 1))

### FIXED CODE ###

import math
N = int(input())
ans = 0
for a in range(1,N):
    ans = ans + math.floor((N - 1)/a)
print(ans)
### BUGGY CODE ###

from bisect import insort_left

n, m = [int(x) for x in input().split()]

a_list = [int(x) for x in input().split()]
a_list.sort()

for _ in range(m):
    a_list[-1] //= 2
    insort_left(a_list, a_list.pop())
print(sum(a_list))

### FIXED CODE ###

import heapq
from math import ceil

n, m = [int(x) for x in input().split()]

a_list = [-int(x) for x in input().split()]
heapq.heapify(a_list)

for _ in range(m):
    temp = ceil(heapq.heappop(a_list) / 2)
    heapq.heappush(a_list, temp)
print(-sum(a_list))
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

for q in range(k):
  b = [0]*(n+1)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
      
  a[0] = b[0]
  for j in range(n-1):
    a[j+1] = a[j] + b[j+1]
  if np.all(a == n):
    break

print(*a)

### FIXED CODE ###

#%%time
from itertools import accumulate
import numpy as np
from numba import njit

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def loop1(a):
  #b = [0]*(n+1)
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  #a = list(accumulate(b))
  #a = a[:-1]
   
  #if np.all(a == n):
   # break

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
ans = 0

for i in range(N):
  for j in range(N):
    if A[i] >= B[j]:
      continue
    for k in range(N):
      if A[i] < B[j] < C[k]:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = [int(b) for b in input().split()]
C = sorted([int(c) for c in input().split()])
ans = 0

import bisect
for i in range(N):
  b = B[i]
  end_A = bisect.bisect_left(A, b)
  start_C = bisect.bisect_right(C, b)
  ans += end_A * (N - start_C)

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

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
  print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [0]
for i in range(n):
  a.append(int(input()))
a.append(0)

l = [0] * (n+2)
l[0] = 0
for i in range(1,n+1):
  l[i] = max(l[i-1], a[i])

r = [0] * (n+2)
r[n] = 0
for i in range(n,0,-1):
  r[i] = max(r[i+1], a[i])

for i in range(1,n+1):
  print(max(l[i-1],r[i+1]))
### BUGGY CODE ###

import collections

n = int(input())
A = list(map(int, input().split()))
B = collections.Counter(A)
D = collections.defaultdict(int)

for k, i in B.items():
    for l, j in B.items():
        if k == l:
            x = (j-1)*(j-2) // 2
            D[k] += x if x > 0 else 0
        else:
            x = j*(j-1) // 2
            D[k] += x if x > 0 else 0

for a in A:
    print(D[a])


### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split()))
B = collections.Counter(A)

s = 0
for k, i in B.items():
    s += i*(i-1) // 2
for a in A:
    print(s-(B[a]-1))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [float('Inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j >= 0:
            if dp[i] > dp[i - j] + abs(a[i] - a[i - j]):
                dp[i] = dp[i - j] + abs(a[i] - a[i - j])
print(dp[n - 1])

### FIXED CODE ###

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

dp = [float('Inf') for _ in range(n)]
dp[0] = 0
for i in range(1, n):
    for j in range(1, k + 1):
        if i - j >= 0:
            if dp[i] > dp[i - j] + abs(a[i] - a[i - j]):
                dp[i] = dp[i - j] + abs(a[i] - a[i - j])
print(dp[n - 1])
### BUGGY CODE ###

a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
table = [i for i in range(2, small + 1) if (i % 2 != 0) and (small % i == 0) and (big % i == 0)]
limit  = math.sqrt(small)
cd = []
if small % 2 == 0 and big % 2 == 0:
    cd.append(2)
while True:
    if len(table) == 0:
        break
    head = table.pop(0)
    if head > limit:
        break
    table = [v for v in table if (v % head != 0) and (small % head == 0) and (big % head == 0)]
    if (small % head == 0) and (big % head == 0):
        cd.append(head)
cd.extend(table)

print(len([i for i in cd if (small % i == 0) and (big % i == 0)]) + 1)


### FIXED CODE ###

a, b = [int(i) for i in input().split()]
small = min(a, b)
big = max(a, b)

import sys

if small == 1:
    print(1)
    sys.exit(0)

import math
import collections

# FYI: https://ja.wikipedia.org/wiki/%E8%A9%A6%E3%81%97%E5%89%B2%E3%82%8A%E6%B3%95
def prime_factorization(num, divisors=None):
    if num <= 1:
        assert False
    factors = []

    # divisorsを使い回せるようにする。
    #   - 二度生成した場合にかかる時間が許容できない場合
    #   - エラトステネスの篩などで素数テーブルを既に持っている場合
    if not divisors:
        divisors = [2] + [i for i in range(3, int(math.sqrt(num)) + 1) if i % 2 != 0]

    for d in divisors:
        # divisorsを引数で与えた場合のみ起こりうる
        if num < d:
            break
        while num % d == 0:
            factors.append(d)
            num //= d

    if num != 1:
        factors.append(num)
    return factors

divisors = [2] + [i for i in range(3, int(math.sqrt(big)) + 1) if i % 2 != 0]
small_factors = set(prime_factorization(small, divisors))
big_factors = set(prime_factorization(big, divisors))

print(len(small_factors.intersection(big_factors)) + 1)
### BUGGY CODE ###

mv=((1,0),(0,1))

def dfs(x,y,ans):
    global res
    ans=max(ans,int(str(ans)+C[y][x]))
    res=max(ans,res)
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>=W or my<0 or my>=H:
            continue
        if C[my][mx].isdigit():
            dfs(mx,my,ans)

while True:
    W,H=map(int,raw_input().split())
    if W==H==0:break
    C=[raw_input() for i in range(H)]
    res=0
    for i in range(H):
        for j in range(W):
            if C[i][j].isdigit() and C[i][j]!="0":
                dfs(j,i,0)
    print res

### FIXED CODE ###

while True:
    W,H=map(int,raw_input().split())
    if W==H==0:break
    C=[raw_input() for i in range(H)]
    table=[[""]*W for i in range(H)]
    ans=0
    for y in range(H):
        for x in range(W):
            if C[y][x].isdigit():
                a,b,c=table[y-1][x],table[y][x-1],C[y][x]
                if a==b=="":
                    table[y][x]=c
                elif a=="":
                    table[y][x]=b+c
                elif b=="":
                    table[y][x]=a+c
                elif int(a)>=int(b):
                    table[y][x]=a+c
                elif int(a)<int(b):
                    table[y][x]=b+c
                ans=ans if ans>int(table[y][x]) else int(table[y][x])
    print ans
### BUGGY CODE ###

N,D,A = map(int,input().split())
d = {}
E = []
for i in range(N):
    x,h = map(int,input().split())
    d[x] = h
    E.append(x)
E.sort()
ans = 0
import bisect
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    z = (d[x]+A-1)//A
    ans += z
    for j in range(i,y):
        d[E[j]] -= z*A
print(ans)

### FIXED CODE ###

N,D,A = map(int,input().split())
attack_number = {}
Enemy = []
import math
for i in range(N):
    x,h = map(int,input().split())
    n = math.ceil(h/A)
    attack_number[x] = n
    Enemy.append(x)
Enemy.sort()
bomb_number = [0 for i in range(N+1)]
F = {}
import bisect
for i in range(N):
    x = Enemy[i]
    y = bisect.bisect_right(Enemy,x+2*D)
    F[i] = y
ans = 0
for i in range(N):
    if i > 0:
        bomb_number[i] += bomb_number[i-1]
    x = attack_number[Enemy[i]] - bomb_number[i]
    if x <= 0:
        continue
    y = F[i]
    bomb_number[i] += x
    bomb_number[y] -= x
    ans += x
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
while True:
  s = s[:-2]
  n -= 2
  if s[:n//2] == s[n//2:]:
    print(n)

### FIXED CODE ###

s = input()
n = len(s)
while True:
  s = s[:-2]
  n -= 2
  if s[:n//2] == s[n//2:]:
    print(n)
    break
### BUGGY CODE ###

from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    S = input()
    LIST = []
    for i in range(2000):
        LIST.append(2019*i)
    start = 0
    cnt = 0
    while start+4 < len(S):
        for i in range(start+4,len(S)+1):
            #print(S[start:i])
            if int(S[start:i]) in LIST:
                cnt += 1
        start += 1
    print(cnt)
if __name__ == '__main__':
  main()


### FIXED CODE ###

S = input()
lenS = len(S)
count = [0] * 2019
count[0] = 1
num = 0
d = 1
for i in range(lenS):
    num += int(S[lenS - i - 1]) * d
    count[num%2019] += 1
    d *= 10
    d %= 2019
ans = 0
for i in count:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = [0] * 60
for x in a:
    x = bin(x)[2:].zfill(60)
    for i in range(60):
        ans[i] += int(x[i])
for i in range(60):
    ans[i] = ans[i] * (n - ans[i]) % mod
    ans[i] = ans[i] * pow(2, 59 - i, mod) % mod
ans_sum = 0
for x in ans:
    ans_sum = (ans_sum + x) % mod
print(ans_sum)

### FIXED CODE ###

import numpy as np
import sys
n = int(input())
a = np.array(sys.stdin.read().split(), dtype=np.int64)
mod = 10 ** 9 + 7
ans = 0
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    x = x * (n - x)
    ans += x * pow(2, i, mod) % mod
print(ans % mod)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

# スタック最大数をセット
sys.setrecursionlimit(10**6)

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

queue = collections.deque()

ans = 0

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    for ddx, ddy in zip(dx, dy):
        if (y+ddy < 0 or h <= y+ddy or x+ddx < 0 or w <= x+ddx or a[y+ddy][x+ddx] == '.'):
            queue.append([y + ddy, x+ddx, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            for ddx, ddy in zip(dx, dy):
                if (i+ddy < 0 or h <= i+ddy or j+ddx < 0 or w <= j+ddx or a[i+ddy][j+ddx] == '.'):
                    queue.append([i + ddy, j+ddx, 0])

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[] for i in range(H)]
for i in range(H):
  st = input()
  for j in range(W):
    maze[i].append(st[j])
queue = deque([[Ch-1, Cw-1, 0]])
inf = float("inf")
table = [[inf for i in range(W)] for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft([dx, dy, cost])
      table[dx][dy] = min(table[dx][dy], table[x][y])
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append([dx, dy, cost+1])
      table[dx][dy] = min(table[dx][dy], table[x][y]+1)

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque

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

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])