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

n = int(input())
s = str(input())

s_r = []
s_g = []
s_b = []

for i in range(n):
  if s[i] == "R":
    s_r.append(i)
  elif s[i] == "G":
    s_g.append(i)
  else:
    s_b.append(i)

def conditions(a, b):
  if (a+b) % 2 == 0:
    x = (a+b) / 2
    y = 2*b - a
    z = 2*a - b
  else:
    x = -1
    y = 2*b - a
    z = 2*a - b
  return (x, y, z)
  
count = 0
for i in range(len(s_r)):
  for j in range(len(s_g)):
    for l in conditions(s_r[i], s_g[j]):
      if l in s_b:
        count += 1
    
ans = len(s_r) * len(s_g) * len(s_b) - count
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for d in range(n):
    j = i + d
    k = j + d
    if k >= n:
      break;
    else:
      a = s[i]
      b = s[j]
      c = s[k]
      if noteq(a, b, c):
        ans -= 1
    
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      for i in range(1, N):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  z=lcm(A,N)
  MOD=10**9+7
  ans=0
  for i in range(N):
    ans+=z//A[i]%MOD
  print(ans%MOD)
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

n  = int(input())

st = input()
num  = []
for i in st:
  if i == "E":
    num.append(1)
  else:
    num.append(0)

mans = 100000000
for i in range(n):
  tmp = i  - sum(num[0:i]) + sum(num[i+1:n])
  
  if tmp<mans:
    mans = tmp
print(mans)
  







"""
upper_bound = n
lower_bound = 0

while upper_bound - lower_bound > 0:
  middle = (upper_bound+ lower_bound) // 2
"""  

### FIXED CODE ###

n = int(input())
st = input()

c = [0] * (n+1)
ans = []
#c[i] == i番目がreaderの時のc[i]より左のEの数
for i in range(len(st)):#i == num_reader
  c[i+1] = c[i]
  if st[i] == "E":
    c[i+1] += 1
for i in range(n):
  e_left = c[i]
  e_right = c[n] - c[i+1]
  ans.append(i-e_left + e_right)
print(min(ans))
### BUGGY CODE ###

import numpy as np


def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = np.zeros((nc + 1, nc + 1), dtype="i8")
    for l, r in t:
        dp[:l + 1, r:] += 1
    for l, r in q:
        print(dp[l][r])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)


### FIXED CODE ###

def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for l, r in t:
        dp[l][r] += 1
    for i in range(1, nc + 1):
        dpi = dp[i]
        s = dpi[0]
        for j in range(1, nc + 1):
            dpi[j] = s = dpi[j] + s
    for j in range(1, nc + 1):
        s = dp[0][j]
        for i in range(1, nc + 1):
            dp[i][j] = s = dp[i][j] + s
    for l, r in q:
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)
### BUGGY CODE ###

s = input()

count = 0
for i,c in enumerate(s):
    if c == "W":
        count += s[:i+1].count("B")

print(count)

### FIXED CODE ###

s = input()

ans = 0
b_count = 0
for i,c in enumerate(s):
    if c == "W":
        ans += b_count
    else:
        b_count += 1

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

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    for i in sorted(Ad.copy().keys()):
        if i >= k:
            break
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)


### FIXED CODE ###

import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
A = list(set(A))
A.sort()
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    ml = bisect.bisect_left(A, k) 
    for i in A[:ml]:
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)
### BUGGY CODE ###

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

ans = 0
sum_j = 0

for i in range(N-1):
  for j in range(i+1,N):
    sum_j += A[j]
  ans += A[i]*sum_j
  sum_j = 0
    

mod = 10**9 + 7
print(ans%mod)

### FIXED CODE ###

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

ans = 0
res = [0] * N
res[0] = A[0]
for i in range(len(A)-1):
    res[i+1] = res[i] + A[i+1]

sum_A = sum(A)

for i in range(N-1):
  ans += A[i]*(sum_A-res[i])
  
mod = 10**9 + 7
print(ans%mod)
### BUGGY CODE ###

l,r = map(int,input().split())

ans = 2019

for i in range(l,r):
  for j in range(i + 1 ,r + 1):
      ans  = min(ans, (i * j) % 2019)
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())

ans = 2019
#差が2018より大きいものは商が必ず1以上になるので、計算の量を減らす
if r - l >= 2018:
  print(0)
else:
  #for文でその他全て計算する
  for i in range(l,r):
    for j in range(i + 1 ,r + 1):
      #余りの最小値を求める
      ans  = min(ans, (i * j) % 2019)
  print(ans)
### BUGGY CODE ###

import itertools

n, c = map(int, input().split())
x = [0] * (n + 1)
v = [0] * (n + 1)
for i in range(1, n + 1):
    x[i], v[i] = map(int, input().split())

ans = 0

for i in range(n + 1):
    d = x[i]
    s = v[:i + 1]
    k = sum(s) - d
    if k > ans:
        ans = k

for j in range(n + 1):
    d = c - x[j]
    s = v[j:]
    k = sum(s) - d
    if k > ans:
        ans = k

for i, j in itertools.combinations(range(1, n + 1), 2):
    d = 2 * x[i] + (c - x[j])
    s = v[:i + 1] + v[j:]
    k = sum(s) - d
    if k > ans:
        ans = k

for i, j in itertools.combinations(range(1, n + 1), 2):
    d = x[i] + 2 * (c - x[j])
    s = v[:i + 1] + v[j:]
    k = sum(s) - d
    if k > ans:
        ans = k

print(ans)

### FIXED CODE ###

from itertools import accumulate

N, C = map(int, input().split())
sushi = [[int(x) for x in input().split()] for _ in range(N)]


def solve():
    """
    O(N)
    Bを固定したときの最適なAを事前に計算
    """
    V = [0] * (N + 1)
    for i in range(N):
        V[i + 1] = V[i] + sushi[i][1]

    f1 = [0] + [V[a + 1] - sushi[a][0] for a in range(N)]
    f2 = [0] + [V[a + 1] - 2 * sushi[a][0] for a in range(N)]

    g1 = [x for x in accumulate(f1, max)]
    g2 = [x for x in accumulate(f2, max)]

    ans = 0
    for j in range(N + 1):
        # OA
        if j == 0:
            i = N
        else:
            i = j - 1

        # OB
        if j == 0:
            ob_x = 0
        else:
            ob_x = C - sushi[j - 1][0]
        ob_v = V[N] - V[j - 1]

        # 2OA + OB
        ans = max(ans, g2[i] + ob_v - ob_x)

        # OA + 2OB
        ans = max(ans, g1[i] + ob_v - 2 * ob_x)
    print(ans)


solve()
### BUGGY CODE ###

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

def estim(n):
    total=0
    for i in range(1,n+1):
        total+=i
    return float(total/n)

final_ans=[]
for i in range(N-K+1):
    ans=0
    for j in  range(i,i+K):
        ans+=(estim(p[j]))
    final_ans.append(ans)

print(max(final_ans))

### FIXED CODE ###

from itertools import accumulate

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

q=[0]+p
q=list(accumulate(q)) 

ans=[]
for i in range(N-K+1):
    ans.append(((q[i+K]-q[i])+K)*0.5)

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

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
b = [0]*(n-len(b))+b
c = list(accumulate([0]+b))

ans = []
for k in range(1,n+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    ans.append(l)

print('\n'.join(map(str,ans)))




### FIXED CODE ###

from collections import Counter
from itertools import accumulate
import bisect

n = int(input())
a = list(map(int, input().split()))
b = sorted(Counter(a).values())
exist = len(b)
b = [0]*(n-exist)+b
c = list(accumulate([0]+b))

print(n)
for k in range(2,n//2+1):
    l = 0
    r = n+1
    while r-l>1:
        x = (r+l)//2
        i = bisect.bisect_left(b,x)
        if c[i]+(n-i)*x>=x*k:
            l = x
        else:
            r = x
    print(l)

for k in range(max(n//2+1,2),n+1):
    if exist>=k:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

n = int(input())

aa = []
for i in range(n):
	k,l = map(int,input().split())
	aa.append([k,l])
dp = [[0,0] for i in range(n+1)]
aa.sort(key = lambda x:x[1])
co = 0
ma = 0
kkk = 0
for i in range(n):
	if i % 2 == 0:
		for j in range(len(aa)):
			if ma < aa[j][0]:
				ma = aa[j][0]
				kkk = j
		co += aa.pop(j)[0]
	else:
		for j in range(len(aa)):
			if ma < aa[j][1]:
				ma = aa[j][1]
				kkk = j
		co -= aa.pop(j)[1]

print(co)

### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n = onem()

po = []
su = 0
for i in range(n):
    a,b = m()
    po.append([a+b,a])
po.sort(reverse = True)

for i in range(n):
    if i % 2 == 0:
        su += po[i][1]
    else:
        su -= po[i][0] - po[i][1]
print(su)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

nums= np.zeros(N+1, dtype=int)
for i, s in enumerate(S):
    if s == ".":
        nums[:i+1] += 1
    else:
        nums[i+1:] += 1

out = nums.min()
print(out)

### FIXED CODE ###

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

penals1 = []
tmp1 = 0
penals2 = []
tmp2 = 0

# 半分まで準備
N_even = (N % 2 == 0)
half_N = N // 2 if N_even else (N-1) // 2 

if N == 1:
    min_val = 0
else:
    for i in range(half_N):
        if S[i] == "#":
            tmp1 += 1
        penals1.append(tmp1)

        if S[N-1-i] == ".":
            tmp2 += 1
        penals2.append(tmp2)

    if N_even:
        min_val = penals1[half_N-1] + penals2[half_N-1] 

        j = 1
        for i in range(half_N, N):
            if S[i] == "#":
                tmp1 += 1
            #penals1.append(tmp1)
            val1 = tmp1 + penals2[half_N-1-j]

            if S[N-1-i] == ".":
                tmp2 += 1
            #penals2.append(tmp2)
            val2 = penals1[half_N-1-j] + tmp2

            min_val = min(min_val, val1, val2)
            j += 1

    else:
        first = True
        j = 0

        # N = (N-1) // 2 + (N-1) // 2 + 1
        for i in range(half_N, N):
            if S[i] == "#":
                tmp1 += 1
            val1 = tmp1 + penals2[half_N-1-j]

            if S[N-1-i] == ".":
                tmp2 += 1
            val2 = penals1[half_N-1-j] + tmp2

            if first:
                min_val = min(val1, val2)
                first = False
            else:
                min_val = min(min_val, val1, val2)
            j += 1

    if S[N-1] == "#":
        tmp1 += 1
    if S[0] == ".":
        tmp2 += 1

    min_val = min(tmp1, tmp2, min_val)
print(min_val)
### BUGGY CODE ###

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

c = 0
colored = [False for _ in range(N)]
Ls = []
for a in A:

    k = -1
    for i, l in enumerate(Ls):
        if l < a and a > k:
            ind = i
            k = a
    if k != -1:
        Ls[ind] = a
    else:
        Ls.append(a)


print(len(Ls))


### FIXED CODE ###

from bisect import bisect_right, bisect_left

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

dp = [1]*N

for a in A:
    ia = bisect_right(dp, -a)
    if dp[ia] == 1:
        dp[ia] = -a
    else:
        ib = bisect_left(dp, -a+1)
        dp[ib] = -a
    #print(dp)

ans = 0
for i in range(N):
    if dp[i] != 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
x = list(map(int,input().split()))
x.append(0)
x.sort()

c = []
for i in range(N - K + 2):
    if (0 not in x[i:i+K+1]) or (len(x[i:i+K+1]) != K+1):
        continue
    p = x[i:i+K+1]
    if min(p) < 0 and max(p) > 0:
        if p[-1] + p[-1] - p[0] < abs(p[0]) + p[-1] -p[0]:
            c.append(p[-1] + (p[-1] - p[0]))
        else:
            c.append(abs(p[0]) + p[-1] - p[0])
    elif min(p) >= 0:
        c.append(p[-1])
    elif max(p) <= 0:
        c.append(abs(p[0]))


print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
### BUGGY CODE ###

import Queue, math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) < l:
        print "OK"
    else:
        que = Queue.PriorityQueue()
        dp = [[1000.0 for i in xrange(n)] for j in xrange(2**n)]
        que.put((0.0, 0, -1))
        while not que.empty():
            co, state, last = que.get()
            if last!=-1 and dp[state][last] < co:
                continue
            for i in xrange(n):
                if (state & (1<<i))==0:
                    nxt = co + math.sqrt(r[last]*r[i])*2.0 if last!=-1 else r[i]
                    if nxt < dp[state | (1<<i)][i]:
                        dp[state | (1<<i)][i] = nxt
                        que.put((nxt, state | (1<<i), i))
        ans = 1000.0
        for i in xrange(n):
            ans = min(ans, dp[2**n-1][i]+r[i])
        print "OK" if ans < l+0.000000001 else "NA"

### FIXED CODE ###

import math
while True:
    l = 0; r = []
    try:
        inp = map(int, raw_input().split())
        l = inp[0]
        r = inp[1:]
    except EOFError:
        break
    n = len(r)
    if 2*sum(r) <= l:
        print "OK"
    else:
        s = []
        if n>1:
            r.sort()
            for i in xrange(n/2):
                s = [r[i]] + s[::-1] + [r[-i-1]]
            if n&1:
                if abs(s[0]-r[n/2]) < abs(s[-1]-r[n/2]):
                    s.append(r[n/2])
                else:
                    s = [r[n/2]] + s
        else:
            s = r
        ans = s[0] + s[-1]
        for i in xrange(n-1):
            ans += 2*math.sqrt(s[i]*s[i+1])
        print "OK" if ans < 0.000000001+l else "NA"
### BUGGY CODE ###

X, K, D = map(int, input().split())
X = abs(X)
for i in range(K):
    if X >= D:
        X = X-D
    elif X < D and (K-i)%2==1:
        X = X-D
        break
    elif X < D and (K-i)%2==0:
        break
print(abs(X))

### FIXED CODE ###

X, K, D = map(int, input().split())
X = abs(X)
dis = X
if X >=D:
    dis = X - D*(min(abs(X)//D,K))
    K = K - min(abs(X)//D,K)
    if K%2==0:
        print(dis)
    else:
        print(abs(dis-D))
else:
    if K%2==0:
        print(dis)
    else:
        print(abs(dis-D))
### BUGGY CODE ###

int1 = lambda x: int(x) - 1
import sys
sys.setrecursionlimit(1000000000)

N, M = map(int, input().split())
edge = [[0]*N for _ in range(N)]
for _ in range(M):
    x, y = map(int1, input().split())
    edge[x][y] += 1

end_point = set()
for x in range(N):
    for y in range(N):
        if edge[x][y] > 0:
            break
    else:
        end_point.add(x)

start_point = set()
for y in range(N):
    for x in range(N):
        if edge[x][y] > 0:
            break
    else:
        start_point.add(y)

# 点i始点のLongest Pathの長さ
def dp(i):
    if i in end_point:
        return 0
    else:
        lp = 0
        for j, flg in enumerate(edge[i]):
            if flg > 0:
                lp = max(lp, dp(j)+1)
        return lp

ans = 0
for x in start_point:
    ans = max(ans, dp(x))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

int1 = lambda x: int(x) - 1

N, M = map(int, input().split())

to_point = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int1, input().split())
    to_point[x].append(y)

dp_memo = [-1]*N
for x in range(N):
    if len(to_point[x]) == 0:
        dp_memo[x] = 0

# 点i始点のLongest Pathの長さ
def dp(i):
    if dp_memo[i] >= 0:
        return dp_memo[i]
    lp = 0
    for j in to_point[i]:
        lp = max(lp, dp(j)+1)
    dp_memo[i] = lp
    return lp

for i in range(N):
    dp(i)

print(max(dp_memo))
### BUGGY CODE ###

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

out = 0

for i in range(n):
    for j in range(i):
        ai = inList[i]
        aj = inList[j]
        if(abs(i-j) == ai + aj):
            out += 1
print(out)


### FIXED CODE ###

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

ml = [0] * n
pl = [0] * n

out = 0

for i in range(0, n):
    if(i+a[i]<n):
        pl[i+a[i]] += 1
    if(i-a[i]>=0):
        ml[i-a[i]] += 1

for i in range(0, n):
    out += pl[i] * ml[i]

print(out)
### BUGGY CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()] + [0 for i in range(K)]

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

print(ans[N-1])


### FIXED CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()] + [0 for i in range(K)]

ans=[10**20 for i in range(N+K)]
ans[0]=0

for i in range(N):
    for j in range(1,K+1):
        ans[i+j]=min(ans[i+j],ans[i]+abs(h[i]-h[i+j]))

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

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

C=0

for i in range(N-1):
	if A.count(A[i-0])==1:
		C=C+0
	else:
		C=C+1

if C==0:
	print('YES')
else:
	print('NO')


### FIXED CODE ###

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

C=0

A.sort()

for i in range(N-1):
    if A[i] == A[i+1]:
        C = C+1
    else:
        C = C

if C == 0:
	print('YES')
else:
	print('NO')
### BUGGY CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
elif 0 in [n % 2019 for n in range(l, r+1)]:
    ans = 0
else:
    m = sorted([(i * j) % 2019 for i in range(l, r) for j in range(i + 1, r + 1)])
    ans = m[0]
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            m =  (i * j) % 2019
            if m == 0:
                print(m)
                exit()
            elif m < ans:
                ans = m
print(ans)
### BUGGY CODE ###

from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    warp_count = 0
    warpq = []
    while q:
        while q:
            warpq.append(q[0])
            h, w = q.popleft()
            if h - 1 >= 0 and t[h - 1][w] > warp_count:
                q.append((h - 1, w))
                t[h - 1][w] = warp_count
            if h + 1 < H and t[h + 1][w] > warp_count:
                q.append((h + 1, w))
                t[h + 1][w] = warp_count
            if w - 1 >= 0 and t[h][w - 1] > warp_count:
                q.append((h, w - 1))
                t[h][w - 1] = warp_count
            if w + 1 < W and t[h][w + 1] > warp_count:
                q.append((h, w + 1))
                t[h][w + 1] = warp_count

        if t[Dh][Dw] != INF:
            break

        warp_count += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > warp_count:
                        ti[j] = warp_count
                        q.append((i, j))
        warpq.clear()

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

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())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

#B
N=int(input())
ans=1
for x in input().split():
    ans*=int(x)

if ans>pow(10,18):
    print("-1")
else:
    print(ans)

### FIXED CODE ###

#B
N=int(input())
ans=1
flag=True
A=[]
for x in input().split():
    A.append(int(x))
    if int(x)==0:
        ans=0

for i in range(N):
    x=A[i]
    ans*=x
    if ans>pow(10,18):
        flag=False
        break

if flag:
    print(ans)
else:
    print("-1")