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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [10**10]*n
def dfs(s):
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    dp[s]=max(1+i+j for i,j in enumerate(sorted(tmp,reverse=1)))
    return dp[s]

dfs(0)
print(dp[0])


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

n = int(input())
a = [0] * n
for i in range(n): a[i] = int(input()) - 1
i = 0
c = 0
ok = False
while i != a[i] and a[i] != 0:
    c += 1
    if a[i] == 1:
        ok = True
        break
    i = a[i]
if ok: print(c)
else: print(-1)


### FIXED CODE ###

n = int(input())
a = [0] * n
for i in range(n): a[i] = int(input()) - 1
i = 0
c = 1
ok = False
s = set()
while a[i] != 1:
    c += 1
    if i in s:
        c = -1
        break;
    s.add(i)
    i = a[i]
print(c)
### BUGGY CODE ###

# from datetime import datetime

# measure_start = datetime.now()

MAX_N = 10000000+1
sos = [1] * (MAX_N+1)
sos[0] = sos[1] = 0
for i in range(2, int(MAX_N**0.5)+1):
    if sos[i]:
        for j in range(i+i, MAX_N+1, i):
            sos[j] = 0

while 1:
    try:
        n = int(input())

        if not n: break
        n -= (n%2 == 1)
        for i in reversed(range(13, n+1)):
            if sos[i] and sos[i-2] and sos[i-6] and sos[i-8]:
                print(i)
                break
    except:
        pass
# measure_stop = datetime.now()
# print(measure_stop - measure_start)

### FIXED CODE ###

# from datetime import datetime

# measure_start = datetime.now()
move = [[[10, 10], [4, 4]], [[8, 2],[4, 2]]]

MAX_N = 10000000+1
sos = [1] * (MAX_N+1)
sos[0] = sos[1] = 0
for i in range(2, int(MAX_N**0.5)+1):
    if sos[i]:
        for j in range(i+i, MAX_N+1, i):
            sos[j] = 0

while 1:
    try:
        n = int(input())

        if not n: break
        n -= (n%2 == 0)
        while n >= 13:
            if sos[n] and sos[n-2] and sos[n-6] and sos[n-8]:
                print(n)
                break
            else:
                n -= move[sos[n-8]][sos[n-6]][sos[n-2]]
    # measure_stop = datetime.now()
    # print(measure_stop - measure_start)
    except:
        pass
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
# print(l)
ans = 0
for i in range(len(l)):
    for j in range(i+1, len(l)):
        k = j + 1
        if k == len(l):
            continue
        if l[i] + l[j] <= l[k]:
            continue
        while k + 1 < len(l) and l[i] + l[j] > l[k+1]:
            k += 1
        ans += k - j

print(ans)
        


### FIXED CODE ###

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

ans = 0
for i in range(len(l)):
    right = i+1
    for left in range(i+1, len(l)):
        while right+1 < len(l) and l[right+1] < l[left] + l[i]:
            right += 1
        ans += right - left
        if right == left:
            right += 1

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

n = int(input())
A = [int(input()) for i in range(n)]
maxv = 0

def f(q, p):
	global maxv
	if q == n:
		if p % 10 != 0 and p > maxv:
			maxv = p
		return
	f(q + 1, p + A[q])
	f(q + 1, p)

f(0, 0)
print(maxv)

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
s = sum(A)
if s % 10:
	print(s)
else:
	A.sort()
	for a in A:
		if a % 10:
			print(s - a)
			exit()
	else:
		print(0)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = []
if n % 2:
    for i in range(n):
        if i % 2 == 0:
            b = [a[i]] + b
        else:
            b.append(a[i])
    print(" ".join(b))
else:
    for i in range(n):
        if i % 2:
            b = [a[i]] + b
        else:
            b.append(a[i])
    print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = input().split()
b = []
for i in range(n - 1, -1, -2):
  b.extend([a[i]])
for j in range(n % 2, n, 2):
  b.extend([a[j]])
print(" ".join(b))
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
cnt=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      #print(i,j,k)
      a=l[i];b=l[j];c=l[k]
      if a<b+c and b<a+c and c<b+a:
        cnt+=1
print(cnt)

### FIXED CODE ###

import bisect
 
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
 
for i in range(n):
  for j in range(i+1,n):
    temp=l[i]+l[j]
    ans+=(bisect.bisect_left(l,temp)-j-1)
print(ans)
### BUGGY CODE ###

N,W = map(int, input().split())
dp = [0] * (W + 1)
nupList = (map(int, input().split()) for _ in range(N))

for w, v in nupList:
    for j in range(W, w - 1, -1 ):
        DP = dp[j - w] + v
        if dp[j] < DP:
            dp[j] = DP

print(dp[W])


### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7
def cmb(n,k,p):
    x,y = 1,1
    for i in range(k):
        x=x*(n-i)%p
        y=y*(i+1)%p
    return x*pow(y,p-2,p)%p

N,K = I()
A = l()
A.sort()
nums = [cmb(N-i-1,K-1,mod) for i in range(N)]
ans = 0
for i in range(N):
    ans = (ans+A[N-i-1]*nums[i])%mod
    ans = (ans-A[i]*nums[i])%mod
print(ans)

### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod=10**9+7
MAX=10**5+100
g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

N,K = I()
A = l()
A.sort()
ans = 0
for i in range(N-K+1):
    ans -= A[i]*cmb(N-i-1,K-1)
    ans %= mod
A = A[::-1]
for i in range(N-K+1):
    ans += A[i]*cmb(N-i-1,K-1)
    ans %= mod
print(ans%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    
    ans *= a[i]
    if ans == 0:
        break
if ans > 10 ** 18:
    ans = '-1'
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from math import gcd

A, B = map(int, input().split())

d = gcd(A, B)
ans = 1
i = 2
while i <= d:
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
print(ans)

### FIXED CODE ###

from math import gcd

A, B = map(int, input().split())

d = gcd(A, B)
ans = 1
i = 2
while i <= pow(d, 1/2)+1:
  if d%i == 0:
    ans += 1
    while d%i == 0:
      d //= i
  i += 1
ans += (d > 1)
print(ans)
### BUGGY CODE ###

import bisect
import numpy as np
n=int(input())
l=list(map(int, input().split()))
l=np.array(l)
l.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans+=bisect.bisect_left(l[j+1:], l[i]+l[j]) #n未満の個数を数える
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))
l.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans+=bisect.bisect_left(l[j+1:], l[i]+l[j]) #n未満の個数を数える
print(ans)
### BUGGY CODE ###

import math

A,B,N=map(int,input().split())
list=[]
t=0
for x in range(N+1):
    y=math.floor(A*x/B)-A*math.floor(x/B)
    if t==0:
        list.append(y)
        t += 1
    else:
        if y  > list[0]:
            list.pop(0)
            list.append(y)
print(list[0])


### FIXED CODE ###

import math

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

if B==1:
    print(0)
else:
    if B > N:
        print(math.floor(A*N/B))

    else:
        print(math.floor(A*(B-1)/B))
### BUGGY CODE ###

As,Aa,Bs,Ba = map(int,input().split())
while Aa > 0 and Ba > 0:
  Bs += -Aa
  As += -Ba

if Bs <= 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math

As,Aa,Bs,Ba = map(int,input().split())
Na = math.ceil(Bs/Aa)
Nb = math.ceil(As/Ba)
 
if Na <= Nb:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7


def f(N, x):
    n = 1
    for i in range(1, N):
        if i != x:
            n *= i
        n %= mod
    return n


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    ans = 0
    r = 0
    for i in range(1, N):
        r += f(N, i)
        ans += D[i-1] * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    r1 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
    r2 = [1]
    for i in range(N-1):
        r2.append(r2[i] * (N-1-i) % mod)

    X = list(map(int, input().split()))
    D = [0 for i in range(N)]
    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    ans = 0
    r = 0
    for i in range(N):
        r += r1[i] * r2[N-i-2]
        ans += D[i] * r
        ans %= mod
    print(ans)


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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, tmp, visited, ret):
        visited[idx] = True
        #print(idx, cur, tmp)

        #tmp[idx] = max(K - cur, 0)
        ret *= max(K - cur, 0)
        ret %= MOD

        cur = min(cur + 1, 2)
        for nex in conn[idx]:
            if not visited[nex]:
                ret = dfs(nex, cur, tmp, visited, ret)
                cur += 1
        return ret

    tmp = [0] * N
    visited = [False] * N
    ret = 1
    ret = dfs(0, 0, tmp, visited, ret)
    #print(tmp)

    #for t in tmp:
    #    ret *= t
    #    ret %= MOD

    print(ret)
    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
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)

    def dfs(idx, cur, tmp, visited, ret):
        visited[idx] = True
        #print(idx, cur, tmp)

        #tmp[idx] = max(K - cur, 0)
        ret *= max(K - cur, 0)
        ret %= MOD

        cur = min(cur + 1, 2)
        for nex in conn[idx]:
            if not visited[nex]:
                ret = dfs(nex, cur, tmp, visited, ret)
                cur += 1
        return ret

    tmp = [0] * N
    visited = [False] * N
    ret = 1
    ret = dfs(0, 0, tmp, visited, ret)
    #print(tmp)

    #for t in tmp:
    #    ret *= t
    #    ret %= MOD

    print(ret)
    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
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

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

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    X = i_input()

    Y = X//100
    L = []
    a = [0,1,2,3,4,5]

    for i in range(1,Y+1):
        c = list(itertools.combinations_with_replacement(a, i))
        for i in c:
            L.append(sum(i))
    Z = X%100
 
    if Z in L:
        print(1)
    else:
        print(0)


 
  
if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    X = i_input()

    Y = X//100
    L = []
    a = [0,1,2,3,4,5]
 
    for i in range(1,min(20,Y)+1):
        c = list(itertools.combinations_with_replacement(a, i))
        for i in c:
            L.append(sum(i))
    Z = X%100
 
    if Z in L:
        print(1)
    else:
        print(0)


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

N = int(input())
A = [int(s) for s in input().split()]

minimum = sum(A)
for i, l in enumerate(A):
  a = sum(A[:i])
  b = sum(A[i:])
  minimum = min(minimum, abs(a-b))
print(minimum)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]

minimum = sum(A)
a = 0
b = minimum
for i, l in enumerate(A):
  a += l
  b -= l
  minimum = min(minimum, abs(a-b))
print(minimum)
### BUGGY CODE ###

n = int(input())

def pcheck(n):
    if n == 1:
        return False
    else:
        root = int(n ** 0.5)
        for i in range(2, root + 1):
            if n % i == 0:
                return False
        return True

if n == 1:
    print('0')
elif pcheck(n) == True:
    print('1')
else:
    rootn = int(n ** 0.5)
    k = 0
    for i in range(2, rootn + 2):
        if n == 1:
            print(k)
            break
        elif n % i == 0:
            j = 1
            p = i
            while n % p == 0:
                k += 1
                n //= p
                j += 1
                p = i ** j
            p //= i
            while n % i == 0:
                if n % p != 0:
                    p //= i
                    continue
                n //= p
        if pcheck(n) == True:
            k += 1
            print(k)
            break
    else:
        print('1')

### FIXED CODE ###

n = int(input())

def pcheck(n):
    if n == 1:
        return False
    else:
        root = int(n ** 0.5)
        for i in range(2, root + 1):
            if n % i == 0:
                return False
        return True

if n == 1:
    print('0')
elif n == 6:
    print('2')
elif pcheck(n) == True:
    print('1')
else:
    rootn = int(n ** 0.5)
    k = 0
    for i in range(2, rootn + 2):
        if n == 1:
            print(k)
            break
        elif n % i == 0:
            j = 1
            p = i
            while n % p == 0:
                k += 1
                n //= p
                j += 1
                p = i ** j
            p //= i
            while n % i == 0:
                if n % p != 0:
                    p //= i
                    continue
                n //= p
    else:
        if pcheck(n) == True:
            k += 1
            print(k)
        else:
            print('1')
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
in_degree = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    in_degree[b] += 1

v_root = in_degree.index(0)

ans = [0] * n
queue = deque([v_root])
while queue:
    v = queue.popleft()
    for v_next in graph[v]:
        ans[v_next] = v + 1
        queue.append(v_next)

print(*ans, sep='\n')


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())

graph = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]
in_degree = [0] * n
out_degree = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph2[b].append(a)
    in_degree[b] += 1
    out_degree[a] += 1

v_root = in_degree.index(0)

depth = [-1] * n
ans = [0] * n
depth[v_root] = 0


def dfs(v):
    if depth[v] == -1:
        for v_par in graph2[v]:
            d = dfs(v_par)
            if depth[v] < d + 1:
                depth[v] = d + 1
                ans[v] = v_par + 1
    return depth[v]


for i in range(n):
    if out_degree[i] == 0:
        # print(i)
        _ = dfs(i)

print(*ans, sep='\n')
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

n = int(input())
L = np.array(list(map(int, input().split())))
s = 0
while True:
    minL = np.min(L[s:])
    m_idx = np.where(L==minL)[0][-1]
    for i in range(s, m_idx):
        if L[i] - minL ==1:
            L[i]-=1
    s = m_idx+1
    
    if s==n:
        break

if np.all(L ==sorted(L)):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())

L = np.array(list(map(int, input().split())))

for i in range(n-1, 0, -1):
    if L[i]-L[i-1] ==-1:
        L[i-1] -=1

if np.all(L ==sorted(L)):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import deque


def solvemaze(y, x, num):
    maps.append([])
    dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
    maze[y][x] = num
    que = deque()
    que.append((y, x))
    while que:
        y_, x_ = que.popleft()
        maps[num].append((y_, x_))
        for i in range(4):
            y2 = y_ + dy[i]
            x2 = x_ + dx[i]
            if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] == '.':
                maze[y2][x2] = num
                que.append((y2, x2))

def makeroute(s_maps, num):
    for y, x in s_maps:
        for i in range(-2, 3):
            for j in range(-2, 3):
                y2 = y + i
                x2 = x + j
                if 0 <= y2 < h and 0 <= x2 < w:
                    num2 = maze[y2][x2]
                    if not  num2 in [0, '#'] + E[num]:
                        E[num].append(num2)
                        E[num2].append(num)
    

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
maps = []

num = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            solvemaze(i, j, num)
            num += 1

E = [[] for _ in range(num)]
for i in range(num):
    makeroute(maps[i], i)

s = maze[Ch-1][Cw-1]
g = maze[Dh-1][Dw-1]
used = [False] * num
used[s] = True
que = deque()
que.append((0, s))
cost = [float('inf')] * num
cost[s] = 0
while que:
    c, v = que.popleft()
    for e in E[v]:
        if not used[e]:
            que.append((c+1, e))
            cost[e] = c+1
            used[e] = True

if not used[g]:
    print(-1)
else:
    print(cost[g])

### FIXED CODE ###

from collections import deque


h, w = map(int, input().split())
Ch, Cw = map(lambda x: int(x)-1, input().split())
Dh, Dw = map(lambda x: int(x)-1, input().split())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if c > maze[y][x]:
        continue
    
    if y == Dh and x == Dw:
        break
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
    for i in range(-2, 3):
        for j in range(-2, 3):
            y3, x3, c2 = y + i, x + j, c+1
            if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                maze[y3][x3] = c2
                que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

class Unbalanced:
	def serchStrings(self,s):
		words=[0 for i in range(26)]
		for i in range(0,len(s)-1):
			words[ord(s[i])-97]+=1
			for j in range(i+1,len(s)):
				words[ord(s[j])-97]+=1
				if max(words)>=len(s[i:j+1])/2+1:
					print i+1,j+1
					return
			words=[0 for i in range(26)]
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=Unbalanced()
	u.serchStrings(s)

### FIXED CODE ###

class nUnbalanced:
	def searchStrings(self,s):
		if len(s)==2:
			x_f=s[0]; x_s=s[1]
			if x_f==x_s: print 1,2; return
			else: print -1,-1; return
		for base in range(len(s)-2):
			x_f=s[base]; x_s=s[base+1]; x_t=s[base+2]
			if x_f==x_s or x_s==x_t or x_f==x_t: print base+1,base+3; return
		print -1,-1

if __name__ == "__main__":
	s=raw_input()
	u=nUnbalanced()
	u.searchStrings(s)