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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


A, B = LI()

AB = [i for i in range(A, B+1)]
#  print(AB)


print(functools.reduce(lambda i, j: int(i) ^ int(j), AB))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


A, B = LI()
# 上から4つまででいい
# 0,3,7,11の順に0になるから。
# じゃあ最大の0は今どこなのか？
if B % 4 == 0:
    # 0になるのが1つ前
    pass
elif B % 4 == 1:
    # 0 になるのが2つ前
    B = B^(B-1)
elif B % 4 == 2:
    # 0になるのが３つ前
    B = B^(B-1)^(B-2)
elif B%4 == 3:
    #  B = B^(B-1)^(B-3)^(B-4)
    B = 0
    
A = A - 1
if A % 4 == 0:
    pass
elif A % 4 == 1:
    A = A ^ (A-1)
elif A % 4 == 2:
    A = A ^ (A - 1) ^ (A - 2)
else:
    #  A = A ^ (A - 1) ^ (A - 2) ^ (A - 3)
    A = 0

#  print(A,B)
print(A^B)
#  print(functools.reduce(lambda i, j: int(i) ^ int(j), AB))
### BUGGY CODE ###

from collections import defaultdict
from itertools import product

n = int(input())
if n < 3:
    print(0)
else:
    rt = int(n ** 0.5)
    if n // rt != rt:
        rt = 0
    factors = defaultdict(int)
    N = n
    n_div = 2
    while n > 1:
        while not n % n_div:
            factors[n_div] += 1
            n = n // n_div
        n_div += 1
        if n == int(n ** 0.5) + 1:
          factors[N] += 1
          break
    lis = [1]
    for k, v in factors.items():
        facts = [k ** i for i in range(v + 1)]
        it = product(lis, facts)
        lis = [a * b for a, b in it]
    nums = [l - 1 for l in lis if l - 1]
    nums = [i for i in nums if (N //i) == (N % i)]
    print(sum(nums))


### FIXED CODE ###

from collections import defaultdict
from itertools import product

n = int(input())
if n < 3:
    print(0)
else:
    rt = int(n ** 0.5)
    factors = defaultdict(int)
    N = n
    n_div = 2
    while n > 1:
        if n_div == int(n ** 0.5) + 2:
            factors[n] += 1
            break
        while not n % n_div:
            factors[n_div] += 1
            n = n // n_div
        n_div += 1
    lis = [1]
    for k, v in factors.items():
        facts = [k ** i for i in range(v + 1)]
        it = product(lis, facts)
        lis = [a * b for a, b in it]
    nums = [l - 1 for l in lis if l - 1]
    nums = [i for i in nums if (N //i) == (N % i)]
    print(sum(nums))
### BUGGY CODE ###

import math
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    count+=max(0,math.ceil((S[i]-B*T)/(A-B)))
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    a=math.ceil((S[i]-B*T)/(A-B))
    if a>0:
      count+=a
    else:
      break
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
 
dp1 = np.array([[0]*T for _ in range(N+1)])
rev_AB = AB[::-1]
dp2 = np.array([[0]*T for _ in range(N+1)])


for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  
  dp1[i,:a] = dp1[i-1,:a]
  dp2[i,:rev_a] = dp2[i-1,:rev_a]
  dp1[i,a:] = np.fmax(dp1[i-1,a:],dp1[i-1,:-a]+b)
  dp2[i,rev_a:] = np.fmax(dp2[i-1,rev_a:],dp2[i-1,:-rev_a]+rev_b)

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])
 
    
print(max(lis))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
@lru_cache(maxsize=None)
def rec(l, r):
	if l > r:
		return 0
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	ret = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return ret

print(rec(0, N-1))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
dp = [[-1]*N for _ in range(N)]

def rec(l, r):
	if l > r:
		return 0
	if dp[l][r] >= 0:
		return dp[l][r]
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	dp[l][r] = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return dp[l][r]

print(rec(0, N-1))
### BUGGY CODE ###

from fractions import gcd
def lcm(a,b):
    return a*b // gcd(a,b)

N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)


### FIXED CODE ###

from fractions import gcd
def lcm(a,b):
    return a*b // gcd(a,b)

N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)
### BUGGY CODE ###

mod=10**9+7
inv2=5*10**8+4
B,W=map(int,input().split())
 
Factorial=[1]*(B+W+1)
for i in range(1,B+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
 
inverseFactorial=[1]*(B+W+1)
inverseFactorial[B+W]=power(Factorial[B+W],mod-2)
for i in range(0,B+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
w,b=[0]*(B+W+1),[0]*(B+W+1)
for i in range(1,B+W+1):
  w[i]=(w[i-1]+comb(i-1,W-1)*power(2,B+W-i))%mod
  b[i]=(b[i-1]+comb(i-1,B-1)*power(2,B+W-i))%mod
ans=[0]*(B+W+1)
#print(w)
#print(b)
for i in range(1,B+W+1):
  ans[i]=(power(2,B+W)+w[i-1]-b[i-1])*power(inv2,B+W+1)
  print(ans[i]%mod)

### FIXED CODE ###

mod=10**9+7
inv2=5*(10**8)+4
B,W=map(int,input().split())
 
Factorial=[1]*(B+W+1)
for i in range(1,B+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
 
inverseFactorial=[1]*(B+W+1)
inverseFactorial[B+W]=power(Factorial[B+W],mod-2)
for i in range(0,B+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
w,b=[0]*(B+W+1),[0]*(B+W+1)
p2=[1]*(B+W+1)
for i in range(1,B+W+1):
  p2[i]=(p2[i-1]*2)%mod
bunbo=power(inv2,B+W+1)  

for i in range(1,B+W+1):
  w[i]=(w[i-1]+comb(i-1,W-1)*p2[B+W-i])%mod
  b[i]=(b[i-1]+comb(i-1,B-1)*p2[B+W-i])%mod
ans=[0]*(B+W+1)
#print(w)
#print(b)
for i in range(1,B+W+1):
  ans[i]=(p2[B+W]+w[i-1]-b[i-1])*bunbo
  print(ans[i]%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
num = list(map(int, input().split()))
max = -((10 ** 9) +7)
for i in range(2 ** n):
    wk = []
    cnt = 0
    numWk = 1
    for j in range(n):
        if ((i>>j) & 1):
            cnt +=1
            wk.append(num[j])
        if cnt > k:
            break
    if cnt == k:
        for j in range(k):
            numWk *= wk[j]
        if max < numWk:
            max = numWk
print(max % ((10 ** 9) +7))


### FIXED CODE ###

import functools

def sign(x):
    if x>0:
        return 1
    elif x==0:
        return 0
    else:
        return -1

def multiply(x,y):
    ans = x*y
    if ans>=10**9+7 or ans<0:
        ans %= (10**9+7)
    return ans

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

if (A[-1]<0 and K%2==1):
    combi = A[-K:]
    if K >1:
        answer =  functools.reduce(multiply,combi)

elif K == N:
    answer = functools.reduce(multiply,A)

else:
    signs = 1
    i,j = 0,0
    for _ in range(K):
        if abs(A[i]) > abs(A[N-j-1]):
            signs *= sign(A[i])
            i += 1

        else:
            signs *= sign(A[N-j-1])
            j += 1
    combi = A[N-j:] + A[:i]
    del A[N-j:]
    del A[:i]
    combi = combi[::-1]

    if signs == -1:
        if A:
            if combi[-1]<0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]>=0:
                del combi[0]
                combi.append(A[-1])
            elif A[0]<0 and A[-1] >0:
                if combi[0]*A[0] > combi[-1]*A[-1]:
                    del combi[-1]
                    combi.insert(0,A[0])
                else:
                    del combi[0]
                    combi.append(A[-1])
            elif A[-1] <= 0:
                del combi[-1]
                combi.insert(0,A[0])

    answer =  functools.reduce(multiply,combi)
print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

while len(d) > 0:
  
  here = d.popleft()
      
  # 右のマス
  if here[1] != W-1:
    if (here[0], here[1]+1) not in score or ((here[0], here[1]+1) in score and (score[(here[0], here[1]+1)] > score[here])):
      if Shw[here[0]][here[1]+1] == ".":
        d.appendleft((here[0], here[1]+1))
        score[(here[0], here[1]+1)] = score[here]

  # 下のマス
  if here[0] != H-1:
    if (here[0]+1, here[1]) not in score or ((here[0]+1, here[1]) in score and (score[(here[0]+1, here[1])] > score[here])):
      if Shw[here[0]+1][here[1]] == ".":
        d.appendleft((here[0]+1, here[1]))
        score[(here[0]+1, here[1])] = score[here]
  
  # 左のマス
  if here[1] != 0:
    if (here[0], here[1]-1) not in score or ((here[0], here[1]-1) in score and (score[(here[0], here[1]-1)] > score[here])):
      if Shw[here[0]][here[1]-1] == ".":
        d.appendleft((here[0], here[1]-1))
        score[(here[0], here[1]-1)] = score[here]
    
  # 上のマス
  if here[0] != 0:
    if (here[0]-1, here[1]) not in score or ((here[0]-1, here[1]) in score and (score[(here[0]-1, here[1])] > score[here])):
      if Shw[here[0]-1][here[1]] == ".":
        d.appendleft((here[0]-1, here[1]))
        score[(here[0]-1, here[1])] = score[here]
  
  # ワープのマス
  for i in range(here[0]-2, here[0]+3, 1):
    if i < 0 or i > H-1:
      continue
    for j in range(here[1]-2, here[1]+3, 1):
      if j < 0 or j > W-1 or (i, j) in score:
        continue
      else:
        if Shw[i][j] == ".":
          d.append((i, j))
          score[(i, j)] = score[here] + 1

#print(score)
if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

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

d.appendleft((Ch-1, Cw-1, 0))
score = [[-1] * W for _ in range(H)]
score[Ch-1][Cw-1] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x, s = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx, s))
          score[y+dy][x+dx] = s
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx, s+1))
          score[y+dy][x+dx] = s+1

print(score[Dh-1][Dw-1])
### BUGGY CODE ###

n = int(input())
a_list = []
b_list = []
for _ in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
a_list = list(reversed(a_list))
b_list = list(reversed(b_list))
ans = 0
for i in range(n):
    a = a_list[i]
    b = b_list[i]
    a += ans
    while (a % b != 0):
        a += 1
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a_list = []
b_list = []
for _ in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
a_list = list(reversed(a_list))
b_list = list(reversed(b_list))
ans = 0
for i in range(n):
    a = a_list[i]
    b = b_list[i]
    a += ans
    if (a % b) != 0:
        ans += b - (a % b)
print(ans)
### BUGGY CODE ###

H, W = map( int, input().split())
P = [ input() for _ in range(H)]
T = [ [1]*W for _ in range(H)]
Y = [ [1]*W for _ in range(H) ]
S = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if P[i][j] == "#":
           S[i][j]  = 1
for i in range(H):
    now = 0
    cnt = 0
    for j in range(W):
        if S[i][j] == 0:
            cnt += 1
        else:
            for k in range(now, j):
                T[i][k] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, W):
                T[i][k] = cnt
            
for i in range(W):
    now = 0
    cnt = 0
    for j in range(H):
        if S[j][i] == 0:
            cnt += 1
        else:
            for k in range(now, j):
                Y[k][i] = cnt
            cnt = 0
            now = j+1
        if cnt > 0:
            for k in range(now, H):
                Y[k][i] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if ans < T[i][j] + Y[i][j]-1:
            ans = T[i][j] + Y[i][j]-1
print(ans)





### FIXED CODE ###

H, W = map( int, input().split())
S = [["#"]*(W+2)]+[ "#"+input()+"#" for _ in range(H)]+ [["#"]*(W+2)]
H += 2
W += 2
L = [[0]*(W+2) for _ in range(H+2)]
R = [[0]*(W+2) for _ in range(H+2)]
D = [[0]*(W+2) for _ in range(H+2)]
U = [[0]*(W+2) for _ in range(H+2)]
cnt = 0

for i in range(1,H-1):
    for j in range(W):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            R[i][j] = cnt
            
for i in range(1,H-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            L[i][j] = cnt

for j in range(1,W-1):
    for i in range(H):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            D[i][j] = cnt

for j in range(1,W-1):
    for i in range(H-1,-1,-1):
        if S[i][j] == "#":
            cnt = 0
        else:
            cnt += 1
            U[i][j] = cnt

ans = 0
for i in range(1,H-1):
    for j in range(1,W-1):
        if ans < L[i][j] + R[i][j] + U[i][j] + D[i][j]:
            ans =  L[i][j] + R[i][j] + U[i][j] + D[i][j]
print(ans-3)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

max_ab = max(AB)
dp = [-1]*(H+max_ab[0]+1)
dp[0] = 0

for i in range(1, H + max_ab[0]):
    lst = [dp[i-AB[j][0]] + AB[j][1] for j in range(N) if (i >= AB[j][0] and dp[i-AB[j][0]]!=-1)]
    if lst!=[]:dp[i] = min(lst)

print(min([i for i in dp[H:-1] if i!=-1]))
               

### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

max_ab = max(AB)
dp = [10**10]*(H+max_ab[0])
dp[0] = 0

for i in range(1, H + max_ab[0]):
    dp[i] = min(dp[i - a] + b for a, b in AB)

print(min(dp[H:]))
### BUGGY CODE ###

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


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos

        for dh, dw in product(range(-2,3), repeat=2):
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()


### FIXED CODE ###

from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()
### BUGGY CODE ###

N=int(input())
A = [int(input()) for i in range(N)] 

for i in range(N):
    print(max(A[:i]+A[i+1:]))

### FIXED CODE ###

N=int(input())
A = [int(input()) for i in range(N)] 

ans=sorted(A, reverse=True)[:2]
for n in A:
    if n == ans[0]:
        print(ans[1])
    else:
        print(ans[0])
### BUGGY CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

from numpy import*
h,*s=open(0)
h,w=int32(h.split())
s,a,b,c,d=eval('int32([[u>"#"for u in t]for t in s]),'*5)
for i in range(w):a[:,i],b[:,~i]=-~a[:,i-1]*s[:,i],-~b[:,-i]*s[:,~i]
for i in range(1,h):c[i,:],d[~i,:]=-~c[i-1,:]*s[i,:],-~d[-i,:]*s[~i,:]
print(amax(a+b+c+d)-3)

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
re = 1
for i in range(N):
  re *= A[i]
if re > 10**18:
  re = -1
print(re)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
re = 1
if int(0 in A) == 1:
  re = 0
  N = 0
for i in range(N):
  re *= A[i]
  if re > 10**18:
    re = -1
    break
print(re)