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

import numpy as np
import decimal
N = int(input())
A = list(map(int, input().split()))

new_A = np.array(A, dtype=np.dtype(decimal.Decimal))
Answer = int(new_A.prod())

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

### FIXED CODE ###


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

B = set(A)
Answer = 1
if 0 in B:
    print(0)
    exit()
for i in range(N):
    Answer *= A[i]
    if Answer > 1000000000000000000:
        print(-1)
        exit()
print(Answer)
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
c=[]
for i in range(a):
    c.append(b.index(i+1)+1)
result = ' '.join(map(str,c))
print(result)

### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c=[0]*a
"""
for i in range(a):
    c.append(b.index(i+1)+1) #おそらく計算量O(N^2)
"""
for i in range(a):
    c[b[i]-1]=i+1
result = ' '.join(map(str,c))
print(result)
### BUGGY CODE ###

import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}

    used = set()
    for _ in range(N+M-1):
        A, B = map(int, input().split())
        d[A].append(B)
        used.add(B)

    root = (set(range(1, N+1))-used).pop()

    q = [(root, 0, 0)]
    parents = [0] * N
    dist = [0] * (N+1)

    while q:
        s, r, x = q.pop()
        if x>dist[s] or r==0:
            dist[s] = x
            parents[s-1] = r
        else:
            continue
        for t in d[s]:
            q.append((t, s, x+1))

    for i in parents:
        print(i)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys
from collections import deque
input=sys.stdin.readline

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
e = {i:[] for i in range(1, N+1)}

l = []
h = [0] * (N+1)

for _ in range(N+M-1):
    A, B = map(int, input().split())
    d[A].append(B)
    e[B].append(A)
    h[B] += 1

st = set()
for i in range(1, N+1):
    if h[i]==0:
        st.add(i)

l = []
while st:
    i = st.pop()
    l.append(i)
    for j in d[i]:
        h[j] -= 1
        if h[j] == 0:
            st.add(j)

tp = {j:i for i,j in enumerate(l, start=1)}
ans = [0] * (N+1)
for i in range(1, N+1):
    s, t = 0, 0
    for j in e[i]:
        if s < tp[j]:
            s = tp[j]
            t = j
    print(t)
### BUGGY CODE ###

a,b,c,k = (int(x) for x in input().split())

while k:
    a,b,c = b+c,a+c,a+b
    k -= 1

ans = a-b

if ans < abs(10**18):
    print(ans)
else:
    print("Unfair")

### FIXED CODE ###

a,b,c,k = (int(x) for x in input().split())

if abs(a-b) > 10 ** 18:
    print('Unfair')
elif a == b:
    print(0)
elif k % 2 == 0:
    print(a-b)
elif k % 2 == 1:
    print(b-a)
### BUGGY CODE ###

# ABC122-C
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
ind = []
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ind.append(i+1)
cnt_list = [0] * N
tmp = 0
for i in range(N):
    if i in ind:
        tmp += 1
    cnt_list[i] = tmp
##print(cnt_list)

for i in range(Q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    print(cnt_list[r] - cnt_list[l])

### FIXED CODE ###

# ABC122-C
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
cnt_list = [0] * N
tmp = 0
for i in range(N-1):
    cnt_list[i] = tmp
    if S[i] == "A" and S[i+1] == "C":
        tmp += 1
cnt_list[N-1] = tmp
##print(cnt_list)
for i in range(Q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    print(cnt_list[r] - cnt_list[l])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
l=b[:n//2]
u=b[n//2:]
for i in a:
  if i in l:
    print(u[0])
  else:
    print(l[-1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
l=b[:n//2]
u=b[n//2:]
for i in a:
  if i <= l[-1]:
    print(u[0])
  else:
    print(l[-1])
### BUGGY CODE ###

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

b = []

for i in a:
    b.append(i)
    b.reverse()
print(' '.join(map(str,b)))

### FIXED CODE ###

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

if n % 2 == 1:
    b = a[::2]
    c = a[1::2]
    b.reverse()
    d = b+c
    print(' '.join(map(str,d)))
else:
    b = a[::2]
    c = a[1::2]
    c.reverse()
    d = c+b
    print(' '.join(map(str,d)))
### BUGGY CODE ###

T = input()
ans = ""
for i in T: 
  if i == "P": ans += "P"
  elif i == "D": ans += "D"
  else: ans += "D"
print(ans)    

### FIXED CODE ###

T = input()
print(T.replace("?","D"))
### BUGGY CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append((r,l,i))

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for r,l,i in qi:
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*((10**6+1)**2)+l*(10**6+1)+i)

    qi.sort()

    ans = [0]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%(10**6+1)
        l = (ist//(10**6+1))%(10**6+1)
        r = ist//(10**6+1)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)


    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()
### BUGGY CODE ###

from heapq import heappush, heappop
from copy import deepcopy

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

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_prev = deepcopy(made)
    tmp = []

    while made_prev:
        made_val = heappop(made_prev)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made, left_val)

    for e in tmp:
        heappush(left, e)

print("Yes")


### FIXED CODE ###

from heapq import heappush, heappop
from copy import deepcopy

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

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_nxt = deepcopy(made)
    tmp = []

    while made:
        made_val = heappop(made)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made_nxt, left_val)

    made = made_nxt

    for e in tmp:
        heappush(left, e)

print("Yes")
### BUGGY CODE ###

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

### FIXED CODE ###

from collections import Counter
n=int(input())
a=Counter(list(map(int,input().split())))
for i in range(n):
    if i+1 in a.keys():
        print(a[i+1])
    else:
        print(0)
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>250000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

N = int(input())
emp = list(map(int,input().split()))
def rem_val(arr, value):
    while value in arr:
        arr.remove(value)

for i in range(N):
    print(emp.count(i+1))
    rem_val(emp,i+1)


### FIXED CODE ###

N = int(input())
emp = list(map(int,input().split()))
ans_l = [0]*(N+1)
for i in range(N-1):
    a = emp[i]
    ans_l[a] +=1
for i in range(1,N+1):
    print(ans_l[i])
### BUGGY CODE ###

K=int(input())


def calc(n):
    x = str(n)
    x = [int(i) for i in x]

    if len(x)==1:
        return True
    for i in range(len(x)-1):
        if abs(x[i] - x[i + 1]) > 1:
            return False
    return True

i=1
t=[]
while True:
    if calc(i):
        t.append(i)
    i+=1
    if len(t)==K:
        break
print(t[-1])

### FIXED CODE ###

K=int(input())
ans=[]
for i in range(1,10):
    ans.append(i)
i=0

while True:
    if ans[i]%10==0:
        ans.append(10*ans[i])
        ans.append(10*ans[i]+1)
    elif ans[i]%10==9:
        ans.append(10*ans[i]+8)
        ans.append(10*ans[i]+9)
    else:
        ans.append(10*ans[i]+(ans[i]%10-1))
        ans.append(10 * ans[i] + (ans[i] % 10 ))
        ans.append(10 * ans[i] + (ans[i] % 10+1))
    if len(ans)>K:
        break
    i+=1

print(ans[K-1])
### BUGGY CODE ###

N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])

### FIXED CODE ###

N,W = [int(i) for i in input().rstrip().split()]
F = [[int(i) for i in input().rstrip().split()] for _ in range(N)]

DP = []
for w,v in F:
    if DP == []:
        DP = [0]*w+[v]*(W-w+1)
    else:
        dp = DP[::]
        for w2 in range(w,W+1):
            dp[w2] = max(DP[w2-w] + v, DP[w2])
        DP = dp
    #print(DP)
print(DP[-1])
### BUGGY CODE ###

def apc001_c():
    import sys
    n = int(input())

    lower = 0
    print(lower)
    sys.stdout.flush()
    seat_low = str(input())
    if seat_low == 'Vacant': return

    upper = n-1
    print(upper)
    sys.stdout.flush()
    seat_up = str(input())
    if seat_up == 'Vacant': return

    while upper - lower >= 2:
        x = (upper + lower) // 2
        print(x)
        sys.stdout.flush()
        s = str(input())
        if s == seat_low: lower = x
        elif s == seat_up: upper = x
        else: return

if __name__ == '__main__':
    apc001_c()

### FIXED CODE ###

def apc001_c():
    import sys
    n = int(input())

    def ask(x:int):
        print(x)
        sys.stdout.flush()
        res = str(input())
        return res

    lower = 0
    seat_low = ask(lower)
    if seat_low == 'Vacant': return

    upper = n-1
    seat_up = ask(upper)
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        s = ask(x)
        if s == 'Vacant': return
        if x % 2 == 0:
            if s == seat_low: lower = x
            else: upper = x
        else:
            if s == seat_up: lower = x
            else: upper = x

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

# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created:  2016-10-07
#

# Usage
#
"""
from __future__ import division
from __future__ import unicode_literals
from __future__ import print_function
from __future__ import absolute_import

def read():
    """Read like as below.
    N A B
    t_1
    t_n
    """
    line_1 = input().split(" ")
    num_of_class = int(line_1[0])
    blocked_class = line_1[1:2]
    blocked_class = range(int(line_1[1]), int(line_1[2]))

    following_class = [int(input()) for _ in range(num_of_class)]

    return following_class, blocked_class


def check_available_class(following_class, blocked_class):
    """Check how many class you can attend.
    >>> check_available_class([4,3,6,9,1], [5,6,7,8])
    4
    >>> check_available_class([5,6,7,8,9], [4,5,6,7,8])
    1
    """
    return len(set(following_class) - set(blocked_class))


if __name__ == "__main__":
    import doctest
    doctest.testmod()

    f, b = read()
    print(check_available_class(f,b))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created:  2016-10-07
#

# Usage
#
"""

def read():
    """Read like as below.
    N A B
    t_1
    t_n
    """
    line_1 = input().split(" ")
    num_of_class = int(line_1[0])
    blocked_class = line_1[1:2]
    blocked_class = range(int(line_1[1]), int(line_1[2]))

    following_class = {int(input()) for _ in range(num_of_class)}

    return following_class, blocked_class


def check_available_class(following_class, blocked_class):
    """Check how many class you can attend.
    >>> check_available_class([4,3,6,9,1], [5,6,7,8])
    4
    >>> check_available_class([5,6,7,8,9], [4,5,6,7,8])
    1
    """
    # return len(set(following_class).difference(blocked_class))
    attendable = [i for i in following_class if not i in blocked_class]
    return len(attendable)

if __name__ == "__main__":
    import doctest
    doctest.testmod()
    f, b = read()
    print(check_available_class(f,b))
### BUGGY CODE ###

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

def main():
    def dfs(i,oi=-1,s=0):
        ans[i]=s+d[i]
        for ki in to[i]:
            if ki==oi:continue
            dfs(ki,i,s+d[i])

    n,q=map(int, input().split())
    to=defaultdict(list)
    d=[0]*n
    ans=[0]*n
    for _ in range(n-1):
        a,b=map(int, input().split())
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)
    for _ in range(q):
        p, x = map(int, input().split())
        d[p-1]+=x
    dfs(0)
    print(*ans)

main()

### FIXED CODE ###

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

def main():
    def dfs(i,oi=-1,s=0):
        ans[i]=s+d[i]
        for ki in to[i]:
            if ki==oi:continue
            dfs(ki,i,s+d[i])

    n,q=map(int, input().split())
    to=defaultdict(list)
    d=[0]*n
    ans=[0]*n
    for _ in range(n-1):
        a,b=map(int, input().split())
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)
    for _ in range(q):
        p, x = map(int, input().split())
        d[p-1]+=x
    dfs(0)
    print(*ans)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]
dq1 = deque([])

while dq:
    r, c, cur_cost = dq.popleft()
    dq1.append((r, c, cur_cost))

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.append((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    if not dq:
        while dq1:
            r, c, cur_cost = dq1.popleft()

            for x in range(-2, 3):
                r_new = r + x
                if r_new < 0 or r_new >= H:
                    continue

                for y in range(-2, 3):
                    c_new = c + y

                    if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                        continue

                    dq.append((r_new, c_new, cur_cost + 1))
                    search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


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

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,th,tw = dot[0],dot[1],dot[2]
        if used_map[th][tw] > -1 and used_map[th][tw] <= tl:
            continue
        used_map[th][tw] = tl

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w):
                    if used_map[th+x][tw+y] == -1 and road_map[th+x][tw+y] == False:
                        if x == y == 0:
                            continue
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[tl,th+x,tw+y])
                        else:
                            heapq.heappush(queue,[tl+1,th+x,tw+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))