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

def main():
  n=int(input())
  a=list(map(int,input().split()))
  v=[ai+1 for ai in a]
  v[-1]-=1
  vs=[1]*n+[0]
  a[-1]-=1
  # 深さnの一本道の木を初期状態とする。
  # a[i]:深さiの葉でまだ木に連結していない葉
  nozero_vs=0
  for i in range(n+1):
    if a[i]==0:
      continue
    if nozero_vs>=i:# a[0]>0のときもここで処理
      print(-1)
      exit(0)
    # 未連結の葉を木にくっつける
    if vs[nozero_vs]>a[i]:
      vs[nozero_vs]-=a[i]
      for j in range(nozero_vs+1,i):
        vs[j]+=a[i]
        v[j]+=a[i]
    elif vs[nozero_vs]==a[i]:
      vs[nozero_vs]=0
      for j in range(nozero_vs+1,i):
        vs[j]+=a[i]
        v[j]+=a[i]
      nozero_vs+=1
    else:
      sum_vs=0
      while sum_vs<a[i]:
        if nozero_vs>=i:
          print(-1)
          exit(0)
        sum_vs+=vs[nozero_vs]
        if sum_vs<a[i]:
          b=vs[nozero_vs]
          vs[nozero_vs]=0
          for j in range(nozero_vs+1,i):
            vs[j]+=b
            v[j]+=b
          nozero_vs+=1
        else:
          b=sum_vs-a[i]
          c=vs[nozero_vs]-b
          vs[nozero_vs]=b
          for j in range(nozero_vs+1,i):
            vs[j]+=c
            v[j]+=c
  print(sum(v))

if __name__=='__main__':
  main()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if n==0:
  if a[0]==1:
    print(1)
    exit()
  else:
    print(-1)
    exit()
if a[0]>0:
  print(-1)
  exit()

ans=1
pre_no_ha=1
all_ha=sum(a)

for ai in a[1:]:
  if pre_no_ha<=0:
    print(-1)
    exit()
  if ai>pre_no_ha*2:
    print(-1)
    exit()
  
  pre_no_ha*=2
  pre_no_ha-=ai
  all_ha-=ai
  pre_no_ha=min(pre_no_ha,all_ha)
  ans+=pre_no_ha+ai

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

from collections import Counter

h, w, n = map(int, input().split())
a_list = [[0 for _ in range(w)] for _ in range(h)]
triangle = []
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 1, a + 2):
        for b_i in range(b - 1, b + 2):
            if (1 <= a_i < h - 1) & (1 <= b_i < w - 1):
                triangle.append(str(a_i) + "_" + str(b_i))
aaa = Counter(triangle).values()
dp = [0 for _ in range(10)]
total = 0
for i in aaa:
    dp[i] += 1
    total += 1
dp[0] = ((h - 2) * (w - 2)) - total
for i in dp:
    print(i)

### FIXED CODE ###

from collections import Counter, defaultdict

ans = defaultdict(lambda: 0)
h, w, n = map(int, input().split())
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 2, a + 1):
        for b_i in range(b - 2, b + 1):
            if (0 <= a_i < h - 2) & (0 <= b_i < w - 2):
                ans[(a_i, b_i)] += 1

k = Counter(ans.values())
print((h - 2) * (w - 2) - sum(k.values()))
for i in range(1, 10):
    if i in k.keys():
        print(k[i])
    else:
        print(0)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  for l1 in range((N-l0*l[0])//l[1]+1):
    l2 = (N - l0*l[0] - l1*l[1])/l[2]
    if l2%1.0 == 0 and l2 >= 0:
      count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
l = sorted([R, G, B])[::-1]

count = 0
for l0 in range(N//l[0]+1):
  n0 = N-l0*l[0]
  for l1 in range(n0//l[1]+1):
    l2 = n0 - l1*l[1]
    if l2%l[2] == 0 and l2 >= 0:
      count += 1
print(count)
### BUGGY CODE ###

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

ans = 1
max_limit = 10 ** 18
for i in range(N):
  ans *= A[i]

if ans > max_limit:
  print(str(-1))
else:
  print(str(ans))

### FIXED CODE ###

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

if ans > max_limit:
  print(str(-1))
else:
  print(str(ans))
### BUGGY CODE ###

N = int(input())
S = []
for n in range(N):
  s = [ss for ss in input()]
  s.sort()
  S.append(s)

ans = 0
for i in range(0, len(S)-1):
  for j in range(i+1, len(S)):
    if S[i] == S[j]:
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = {}
for n in range(N):
  s = [ss for ss in input()]
  s.sort()
  s_join = "".join(s)
  if s_join not in S.keys():
    S[s_join] = 1
  else: #s_join in S.keys():
    S[s_join] += 1

ans = 0
for k in S.values():
  if k == 1:
    continue
  else:
    ans += sum(range(1, k))

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

n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
  p[i]=p[i]/2+0.5
  ans=sum(p[:k])
  now=sum(p[:k])
for i in range(n-k):
  now=now-p[i]+p[i+k]
  ans=max(ans,now)
print(ans)
 
 
 
 
 
 
 
 
 
 

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	p=LI()

	for i in range(n):
		p[i]=p[i]/2+0.5
	#print(p)

	ans=sum(p[:k])
	now=sum(p[:k])

	for i in range(n-k):
		now=now-p[i]+p[i+k]
		ans=max(ans,now)
	print(ans)















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

k = int(input())

if k % 2 ==0:
    print(-1)
else:
    ans = 1
    tempmod = 0
    while True:
        tempmod = (tempmod + 7*pow(10, ans-1, k)) % k
        if tempmod == 0:
            print(ans)
            exit()
        else:
            ans = ans + 1


### FIXED CODE ###

k = int(input())

if k % 2 ==0 or k % 5 == 0:
    print(-1)
else:
    ans = 1
    tempmod = 0
    while True:
        tempmod = (tempmod + 7*pow(10, ans-1, k)) % k
        if tempmod == 0:
            print(ans)
            exit()
        else:
            ans = ans + 1
### BUGGY CODE ###

import sys
from math import factorial

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

mod = 10**9 + 7

a.sort()

li = []
for i in range(n-1):
    li.append(a[i+1]-a[i])

ans = 0

dp = [1]
for i in range(1,n+1):
    dp.append(dp[-1]*i%mod)

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) % mod

    return result

comb1 = comb(n,k)

for i in range(n-1):
    if i+1 < k and n-i-1 < k:
        ans += li[i] * comb1
    elif i+1 < k:
        ans += li[i] * (comb1 - comb(n-i-1,k))
    elif n-i-1 < k:
        ans += li[i] * (comb1 - comb(i+1,k))
    else:
        ans += li[i] * (comb1 - comb(n-i-1,k) - comb(i+1,k))

print(ans%mod)


### FIXED CODE ###

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

mod = 10**9 + 7

a.sort(reverse = True)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(100010)
ans = 0

for i in range(n-k+1):
    ans += a[i] * comb(n-i-1, k-1)
    ans %= mod

a = a[::-1]

for i in range(n-k+1):
    ans -= a[i] * comb(n-i-1, k-1)
    ans %= mod

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

n=int(input())
A=list(map(int,input().split()))
sum=1
for i in A:
    sum=sum*i
if sum>1000000000000000000:
    print(-1)
else:
    print(sum)


### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
    exit()

for i in A:
   ans=ans*i
   if ans>10**18:
    print(-1)
    exit()


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

n = int(input())

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

if n % 2 == 0:
    b = 0
    for i in range(n//2):
        if a.count(i*2+1) != 2:
            b = 1
    if b == 1:
        print(0)
    else:
        print(2**(n//2))
else:
    b = 0
    if a.count(0) != 1:
        b = 1
    else:
        for i in range(n//2):
            if a.count((i+1)*2) != 2:
                b = 1
    if b == 1:
        print(0)
    else:
        print(2**(n//2))

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
a.sort()
if n % 2 == 0:
    b = 0
    for i in range(0,n,2):
        if a[i] != a[i+1] and a[i] != i+1:
            b = 1
    if b == 1:
        print(0)
    else:
        print((2**(n//2))%1000000007)
else:
    b = 0
    if a[0] != 0:
        b = 1
    else:
        for i in range(1,n,2):
            if a[i] != a[i+1] and a[i] != i+1:
                b = 1
    if b == 1:
        print(0)
    else:
        print((2**(n//2))%1000000007)
### BUGGY CODE ###

x,n = map(int,input().split())
P = list(map(int,input().split()))
i = 0
while True:
    ans = x - i
    if ans in P:
        ans = x + i
        if ans in P:
            continue
        else:
            print(ans)
            break
    else:
        print(ans)
        break
    i = i + 1

### FIXED CODE ###

x,n = map(int,input().split())
P = list(map(int,input().split()))
i = 0
if not x in P:
    print(x)
else:
    while True:
        ans = x - i
        if not ans in P:
            print(ans)
            break
        else:    
            ans = x + i
            if not ans in P:
                print(ans)
                break
        i = i + 1
### BUGGY CODE ###

from collections import deque

d = deque()
def f(tree, counter, arr, n):
  global d
  if not arr:
    return
  for pp in arr if type(arr) == list else arr.popleft():
    if isinstance(tree[pp], list):
      if tree[pp]:
        d.append(tree[pp])
    counter[pp] += n
  if d:
    return f(tree, counter, d, n)

def main():
  N, Q = na()

  tree = [[] for _ in range(N+1)]
  for _ in range(N-1):
    a, b = na()
    tree[a] += [b]

  counter = [0] * (N+1)
  for _ in range(Q):
    p, x = na()
    f(tree, counter, tree[p], x)
    counter[p] += x
  print(*counter[1:])

if __name__ == "__main__":
  import sys
  sys.setrecursionlimit(10000000)

  stdin = sys.stdin
  na = lambda: map(int, stdin.readline().split())
  main()

### FIXED CODE ###

import sys

stdin = sys.stdin
na = lambda: map(int, stdin.readline().split())

def main():
  N, Q = na()

  ab = []
  for _ in range(N-1):
    a, b = na()
    ab.append([a, b])
  ab.sort()

  counter = [0] * (N+1)
  for _ in range(Q):
    p, x = na()
    counter[p] += x
  for i in range(N - 1):
    counter[ab[i][1]] += counter[ab[i][0]]
  print(*counter[1:])

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

def main():
    import copy
    H,W,K=map(int,input().split())
    S=[]
    for _ in range(H):
        S.append([int(x) for x in list(input())])

    ans=(H-1)+(W-1)

    for i in range(2**(H-1)):
        check=[0]*H
        for j in range(H-1):
            if ((i>>j)&1):
                check[j+1]=check[j]+1
            else:
                check[j+1]=check[j]
        
        g=check[H-1]+1
        A=[0]*g
        c=0
        f=0
        for j in range(W):
            B=[0]*g
            for k in range(H):
                if S[k][j]==1:
                    B[check[k]]+=1
                if B[check[k]]>K:
                    c=10**4
                    f=1
                    break
            if f:
                break
            #print("AB",A,B)
            for l in range(g):
                if B[l]==0:
                    continue
                elif A[l]+B[l]>K:
                    c+=1
                    A=copy.copy(B)
                    break
                else:
                    A[l]+=B[l]
        ans=min(ans,c+g-1)

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

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

import sys
input = sys.stdin.readline
    
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
mul=1
for i in range(1,length):
    for j in range(13):
        if dp[i-1][j] != 0:
            if S[length-i-1] == "?":
                for k in range(10):
                    j_sub = j+k*mul%13
                    if j_sub > 12: j_sub-=13
                    dp[i][j_sub]+=dp[i-1][j]
            else: 
                j_sub = j+int(S[length-i-1])*mul%13
                if j_sub > 12: j_sub-= 13
                dp[i][j_sub]+=dp[i-1][j]
    mul=mul*10
print(dp[length-1][5]%1000000007)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = {(A[0], 0), (A[k], k)}

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            dp[k] |= dp[k - rm]
        ss = sorted(dp[k])
        dp[k] = {ss[-1], ss[-2]}

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

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

for i in range(1,N+1):
    s=a.count(i)
    print(s)

### FIXED CODE ###

import collections
N=int(input())
a=list(map(int,input().split()))

c = collections.Counter(a)

for s in range(1,N):
    if s in c:
        print(c[s])
    else:
        print("0")
print("0")
### BUGGY CODE ###

N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = []
    count = 1
    for i in range(1,len(s)):
        if s[i-1] == s[i]:
            count += 1
        if s[i-1] != s[i]:
            s2.append(count)
            count = 1
    s2.append(count)
    if s[0] != '1':
        s2.insert(0,0)
    if s[-1] != '1':
        s2.append(0)
    ans2 = 0
    K2 = 2*K+1
    for i in range(0,max(1,len(s2) - K2 +1),2):
        ans2 = max(ans2,sum(s2[i:i+K2]))
    print(ans2)

### FIXED CODE ###

N,K = map(int,input().split())
s=input()
if '0' not in s:
    print(len(s))
else:
    s2 = [0]
    count = 0
    for i in range(len(s)-1):
        count += 1
        if s[i] != s[i+1]:
            s2.append(count)
    s2.append(count+1)
    if s[0] == '0':
        s2.insert(0,0)
    ans = 0
    for i in range(0,len(s2)-1,2):
        ans = max(ans,s2[min(len(s2)-1,i+2*K+1)] - s2[i])
    print(ans)
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	rows, cols = rli()
	r0, c0 = rli(); r0 -= 1; c0 -= 1;
	r1, c1 = rli(); r1 -= 1; c1 -= 1;
	G = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "#": 
				row.append(1)
			else:
				row.append(0)
		G.append(row)

	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols	
	seen = defaultdict(lambda: False)
	Q = [] #(num magics, r, c)
	heappush(Q, (0, r0, c0))
	ans = INF
	while Q:
		magics, r, c = heappop(Q)
		if seen[(r, c)]: continue
		seen[(r, c)] = True
		if r == r1 and c == c1:
			ans = magics
			break
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr, nc = r + dr, c + dc 
				if not inside(nr, nc) or G[nr][nc] == 1 or seen[(nr, nc)]: continue
				n_magics = magics 
				if abs(dr) + abs(dc) > 1:
					n_magics += 1
				heappush(Q, (n_magics, nr, nc))
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	rows, cols = rli()
	r0, c0 = rli(); r0 -= 1; c0 -= 1;
	r1, c1 = rli(); r1 -= 1; c1 -= 1;
	G = []
	for _ in range(rows):
		row = []
		for c in rll()[0]:
			if c == "#": 
				row.append(1)
			else:
				row.append(0)
		G.append(row)

	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols	
	seen = [0 for _ in range(rows*cols+10)]
	Q = deque() #(num magics, r, c)
	Q.append((0, r0, c0))
	ans = INF
	while Q:
		magics, r, c = Q.pop()
		val = r*cols + c 
		if seen[val]: continue
		seen[val] = True
		if r == r1 and c == c1:
			ans = magics 
			break
		for dr in range(-2, 3):
			for dc in range(-2, 3):
				nr, nc = r + dr, c + dc 
				if not inside(nr, nc) or seen[cols*nr + nc] or G[nr][nc] == 1: continue
				if abs(dr) + abs(dc) > 1:
					Q.appendleft((magics+1, nr, nc))
				else:
					Q.append((magics, nr, nc))
	print(ans if ans < INF else -1)
	stdout.close()

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

s=input()

k = 10**100
logk = k.bit_length()
lens = len(s)
doubling = [[0]*lens for _ in range(logk)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

for i in range(1,logk):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
for pos in range(logk):
  if k & 1:
    now = doubling[pos][now]
  k = k >> 1

result = [0] * lens
for i in range(lens):
  result[i] = doubling[logk-1].count(i)
  print(result[i])

### FIXED CODE ###

s=input()

logk = (10**100).bit_length()
lens = len(s)
logs = lens.bit_length()
doubling = [[0]*lens for _ in range(logk)]

for i in range(lens):
  if s[i] == 'R':
    doubling[0][i] = i + 1
  else:
    doubling[0][i] = i - 1

for i in range(1,logk):
  for j in range(lens):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

from collections import Counter
result = Counter(doubling[logk-1])
for i in range(lens):
  print(result[i])
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    tmpS = S
    T = input().split()
    if T[0] == "1":
        S = tmpS[::-1]
    if T[0] == "2":
        if T[1] == "1":
            S = T[2] + tmpS
        if T[1] == "2":
            S = tmpS + T[2]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

jun = True
head = ""

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            head += T[2]
            continue

        else:
            S += T[2]

if jun:
    print(head[::-1] + S)
else:
    print(S[::-1] + head)
### BUGGY CODE ###

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

mid_n = len(a)//2
for i in range(n):
    if a.index(x[i]) < mid_n:
        print(a[mid_n])
    else:
        print(a[mid_n-1])

### FIXED CODE ###

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

mid_n = len(a)//2
right = a[mid_n]
left = a[mid_n-1]

for i in range(n):
    if right > x[i]:
        print(right)
    else:
        print(left)
### BUGGY CODE ###

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

ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        ans += a[i]*a[j]
        ans %= int(1e9+7)
        
print(ans)

### FIXED CODE ###

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

ans = 0
latsum = sum(a)-a[0]
for i in range(n-1):
    ans += a[i]*latsum
    ans %= int(1e9+7)
    latsum -= a[i+1]
        
print(ans)