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

import numpy as np
n = int(input())
a = list(map(int,input().split()))
keisuu = [[0]*n for _ in range(n)]
for i in range(n):
    a[i]*=2
    
    if i+1 <=n-1:
        keisuu[i][i+1] = 1
        keisuu[i][i] = 1
    else:
        keisuu[i][i] = 1
        keisuu[i][0] = 1
keisuu = np.array(keisuu)
avec = np.array(a)
inv_keisuu = np.linalg.inv(keisuu)
x = np.dot(inv_keisuu,avec)
for i in range(n):
    print(int(x[i]))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
x = s-2*sum([a[i] for i in range(1,n-1,2)])
print(x)
for i in range(n-1):
    x = 2*a[i]-x
    print(x)
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = list(input())[:-1]

	p=''
	pi=-1
	is_exist_st=False
	#pa(s)
	for i, c in enumerate(s):
		if p == 'S' and c == 'T':
			s[pi] = 'e'
			s[i] = 'e'
			#print(s)
			is_exist_st = True
			p=''
			for bj in range(i):
				if s[i-1-bj]!='e':
					p=s[i-1-bj]
					pi=i-1-bj
					break
		else:
			p=c
			pi=i
	return len(s)-s.count('e')
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = list(input())[:-1]

	count_s = 0
	delete_num=0
	for c in s:
		if c == 'S':
			count_s+=1
		else: #if c == 'T':
			if count_s == 0:
				pass
			else:
				count_s-=1
				delete_num+=2
	return len(s)-delete_num
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

cnt=0
for i in range(N+1):
    for j in range(N+1):
        if N-(R*i+G*j)>=0 and (N-(R*i+G*j))%B==0:
            cnt+=1
        if R*i+G*j>N:
            break

    if R*i>N:
        break

print(cnt)


### FIXED CODE ###

R,G,B,N=map(int,input().split())

cnt=0
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        if (N-(R*i+G*j))%B==0:
            cnt+=1

print(cnt)
### BUGGY CODE ###

import sys
import math
from collections import deque
from collections import defaultdict

def main():
    n, k = list(map(int,sys.stdin.readline().split()))
    p = list(map(int,sys.stdin.readline().split()))
    sum_max = 0
    max_idx = 0
    for i in range(n - k + 1):
        max_tmp = 0
        for j in range(k):
            max_tmp += p[i+j]
        if sum_max < max_tmp:
            max_idx = i
            sum_max = max_tmp
    #print(max_idx)
    ans = 0
    sigma = [i for i in range(1,1000)]
    for i in range(max_idx, max_idx + k):
        ans += sum(sigma[:p[i]]) / p[i]
    print("{:.12f}".format(ans))
    return 0

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import defaultdict

def main():
    n, k = list(map(int,sys.stdin.readline().split()))
    p = list(map(int,sys.stdin.readline().split()))
    sum_l = [0] * (n - k + 1)
    for i in range(k):
        sum_l[0] += p[i]
    for i in range(1,n - k + 1):
        sum_l[i] = sum_l[i - 1] - p[i - 1] + p[i + k - 1]
    #print(sum_l)
    max_idx = sum_l.index(max(sum_l))
    #print(max_idx)
    ans = 0
    for i in range(max_idx, max_idx + k):
        ans += ((p[i] * (p[i] + 1)) / 2) / p[i]
    print("{:.12f}".format(ans))
    return 0
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,W = map(int,input().split())
ans = [[0,0]]
ans_fin = 0
for i in range(N):
    w,v = map(int,input().split())
    for j in range(len(ans)):
        if ans[j][0] + w <= W:
            ans.append([ans[j][0]+w,ans[j][1]+v])
            ans_fin = max(ans_fin,ans[j][1]+v)
print(ans_fin)

### FIXED CODE ###

N,W = map(int,input().split())
dp = [0]*(W+1)
for i in range(N):
    w,v = map(int,input().split())
    for i in range(W,w-1,-1):
        dp[i] = max(dp[i],dp[i-w]+v)
print(dp[-1])
### BUGGY CODE ###

import sys


def answerA():
    input = sys.stdin.readline
    N = int(input())

    print((N-1) // 2)


def answer():
    input = sys.stdin.readline
    N = int(input())
    distances = list(map(int, input().split()))

    maximum = max(distances)
    counts = []

    for d in range(maximum + 1):
        counts.append(distances.count(d))

    result = 1
    mod = 998244353

    if 0 in counts:
        result = 0
    elif 0 in distances[1:]:
        result = 0
    else:
        for d in distances[1:]:
            result *= counts[d-1]
            result %= mod

    print(result)


if __name__ == '__main__':
    answer()


### FIXED CODE ###

def answer():
    N = int(input())
    distances = list(map(int, input().split()))

    result = 1
    mod = 998244353

    if distances[0] != 0:
        result = 0
    elif 0 in distances[1:]:
        result = 0
    else:
        distances.sort()
        maximum = distances[-1]
        counts = [0] * (maximum + 1)
        counts[0] = 1
        for d in distances[1:]:
            counts[d] += 1
            result *= counts[d-1]
            result %= mod

    print(result)


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

n, q = list(map(int, input().split(" ")))
a = []
b = []
tree = []

class Node:
    def __init__(self, id):
        self.id = id
        self.counter = 0
        self.linked = []

    def add_node(self, node):
        self.linked.append(node)

    def add_count(self, count):
        self.counter += count

# make node
for i in range(n):
    tree.append(Node(i))
# add node
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_node(tree[k-1])

# add count
for i in range(q):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_count(k)

# traverse
for i in tree:
    for j in i.linked:
        j.counter += i.counter

m = []
for i in tree:
    m.append(i.counter)

print(" ".join(map(str, m)))


### FIXED CODE ###

n, q = list(map(int, input().split(" ")))
a = []
b = []
tree = []

class Node:
    def __init__(self, id):
        self.id = id
        self.counter = 0
        self.linked = []

    def add_node(self, node):
        self.linked.append(node)

    def add_count(self, count):
        self.counter += count

# make node
for i in range(n):
    tree.append(Node(i))

# add node
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_node(tree[k-1])

# add count
for i in range(q):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_count(k)

# traverse
for i in tree:
    for j in i.linked:
        j.counter += i.counter

m = []
for i in tree:
    m.append(i.counter)

print(" ".join(map(str, m)))
### BUGGY CODE ###


import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)

def acinput():
    return list(map(int, input().split(" ")))


N=input()
a=sorted(acinput())

res=1

for sa in a:
    res*=sa
    if res>10**18:
        res=-1
        
    
print(res)


### FIXED CODE ###


from functools import *
import sys
sys.setrecursionlimit(100000)

def acinput():
    return list(map(int, input().split(" ")))


N=input()
a=acinput()

if min(a)==0:
    print(0)
    sys.exit()
res=1

for sa in a:
    res*=sa
    if res>10**18:
        res=-1
        break
        
    
print(res)
### BUGGY CODE ###

r, c, k = map(int, input().split())
v = [[0]*(c+1) for i in range(r+1)]
for i in range(k):
    cr, cc, cv = map(int, input().split())
    v[cr][cc] = cv

dp = [[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for cr in range(1, r+1):
    for cc in range(1, c+1):
        for cn in range(4):
            upper = max(dp[cr-1][cc][0], dp[cr-1][cc][1], dp[cr-1][cc][2], dp[cr-1][cc][3])
            if cn == 0:
                # print(cr, cc, upper)
                dp[cr][cc][cn] = max(upper, dp[cr][cc-1][cn], dp[cr][cc][cn])
            elif cn == 1:
                dp[cr][cc][cn] = max(dp[cr][cc-1][cn], dp[cr][cc-1][cn-1]+v[cr][cc], upper++v[cr][cc])
            else:
                dp[cr][cc][cn] = max(dp[cr][cc-1][cn], dp[cr][cc-1][cn-1]+v[cr][cc])

print(max(dp[r][c]))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

r, c, k = map(int, input().split())
v = [[0]*(c+1) for i in range(r+1)]
for i in range(k):
    cr, cc, cv = map(int, input().split())
    v[cr][cc] = cv

dp = [[0]*4 for _ in range(c+1)]
last = [[0]*4 for _ in range(c+1)]
for cr in range(1, r+1):
    for cc in range(1, c+1):
        upper = max(last[cc][0], last[cc][1], last[cc][2], last[cc][3])
        dp[cc][0] = max(upper, dp[cc-1][0], dp[cc][0])
        dp[cc][1] = max(dp[cc-1][1], dp[cc-1][0]+v[cr][cc], upper+v[cr][cc])
        dp[cc][2] = max(dp[cc-1][2], dp[cc-1][1]+v[cr][cc])
        dp[cc][3] = max(dp[cc-1][3], dp[cc-1][2]+v[cr][cc])
        last = dp
print(max(dp[c]))
### BUGGY CODE ###

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

H,W = map(int,input().split())

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))

q = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

ans = -1
while q:
  qq = []
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  ans += 1
  
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

from scipy.sparse import*
f=csgraph.floyd_warshall
I=9e9
i=lambda:map(int,input().split())
n,m,l=i()
d=eval('[I]*-~n,'*-~n)
while m:a,b,c=i();d[a][b]=c;m-=1
d=f(d,0)
d[d>l]=I
d[d<I]=1
d=f(d)
q,=i()
while q:s,t=i();print((I>d[s,t])*int(d[s,t])-1);q-=1

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

N,K = map(int,input().split())
b = K
r = N-K
mod = 10**9+7
# rのしきりr+1にi個いれる→(r+1)Ci
# bはしきりb-1にi-1個入れる→(b-1)C(i-1)

for i in range(1,K+1):
    ans = 1
    for j in range(1,i):
        ans *= (r+1)-(j-1)
        ans *= (b-1)-(j-1)
        ans *= pow(j,mod-2,mod)
        ans *= pow(j,mod-2,mod)
        ans %= mod
    ans *= (r+1)-(i-1)
    ans *= pow(i,mod-2,mod)
    ans %= mod
    print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
b = K
r = N-K
mod = 10**9+7
# rのしきりr+1にi個いれる→(r+1)Ci
# bはしきりb-1にi-1個入れる→(b-1)C(i-1)

ans = (r+1)
print(ans)
for i in range(2,K+1):
    ans *= (r+1)-(i-1)
    ans *= (b-1)-(i-2)
    ans *= pow(i,mod-2,mod)
    ans *= pow(i-1,mod-2,mod)
    ans %= mod
    print(ans)
### BUGGY CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
        c=deque()    
        s=0
        c.append(i)
        c.append(j)
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        S[m][n]=s
                        for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                          if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                          if T[kk]==1:continue
                          if S[kk] == 0:
                            c.append(kk[0])
                            c.append(kk[1])
                        
 
        #print(T)
        d = max(d,s)
        S=np.zeros_like(T,dtype=int)
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

n = int(input())

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

CountList = list(range(n))
summ = 0
for i in range(n):
    summ += List.count(i+1)
    if summ < n:
        CountList[i] = List.count(i+1)
    else:
        CountList[i] = 0


for j in CountList:
    print(j)

### FIXED CODE ###

import collections

n = int(input())
List = list(map(int, input().split()))
Col = collections.Counter(List)
Col2 = sorted(Col.items())
CountList = [0]*n
for i in Col2:
    CountList[i[0]-1] = i[1]
#CountList = list(Col2.values()) 
#for i in range(n-len(CountList)):
#    CountList.append(0)

for i in CountList:
    print(i)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
list_a=list(map(int,input().split()))
list_b=list(map(int,input().split()))
list_c=list(map(int,input().split()))
list_a.sort(reverse=True)
list_b.sort(reverse=True)
list_c.sort(reverse=True)
dict_p={}
dict_p[(0,0,0)]=list_a[0]+list_b[0]+list_c[0]
pop_list=[]
for i in range(0,k):
    Max=max(dict_p.values())
    print(Max)
    for j in dict_p:
        if dict_p[j]==Max:
            now=j
            dict_p.pop(now)
            pop_list.append(now)
            break
    if now[0]+1<x:
        x_t=1
        for i in pop_list:
            if (now[0]+1,now[1],now[2])==i:
                x_t=0
        if x_t==1:
            dict_p[(now[0]+1,now[1],now[2])]=list_a[now[0]+1]+list_b[now[1]]+list_c[now[2]]
    if now[1]+1<y:
        y_t=1
        for i in pop_list:
            if (now[0],now[1]+1,now[2])==i:
                y_t=0
        if y_t==1:
            dict_p[(now[0],now[1]+1,now[2])]=list_a[now[0]]+list_b[now[1]+1]+list_c[now[2]]
    if now[2]+1<z:
        z_t=1
        for i in pop_list:
            if (now[0],now[1],now[2]+1)==i:
                z_t=0
        if z_t==1:
            dict_p[(now[0],now[1],now[2]+1)]=list_a[now[0]]+list_b[now[1]]+list_c[now[2]+1]
    


### FIXED CODE ###

x,y,z,k=map(int,input().split())
list_a=list(map(int,input().split()))
list_b=list(map(int,input().split()))
list_c=list(map(int,input().split()))
list_a.sort(reverse=True)
list_b.sort(reverse=True)
list_c.sort(reverse=True)
dict_p={}
dict_p[(0,0,0)]=list_a[0]+list_b[0]+list_c[0]
pop_list=[]
for i in range(0,k):
    Max=max(dict_p.values())
    print(Max)
    for j in dict_p:
        if dict_p[j]==Max:
            now=j
            dict_p.pop(now)
            pop_list.append(now)
            break
    if now[0]+1<x:
        if not (now[0]+1,now[1],now[2]) in pop_list:
            dict_p[(now[0]+1,now[1],now[2])]=list_a[now[0]+1]+list_b[now[1]]+list_c[now[2]]
    if now[1]+1<y:
        if not (now[0],now[1]+1,now[2]) in pop_list:
            dict_p[(now[0],now[1]+1,now[2])]=list_a[now[0]]+list_b[now[1]+1]+list_c[now[2]]
    if now[2]+1<z:
        if not (now[0],now[1],now[2]+1) in pop_list:
            dict_p[(now[0],now[1],now[2]+1)]=list_a[now[0]]+list_b[now[1]]+list_c[now[2]+1]
### BUGGY CODE ###

s=int(input())
a=list(map(int,input().split()))
b=[]*s
if s%2==0:
  for i in range(0,s):
    if i%2==0:
      b.append(a[i])
    if i%2!=0:
      b.insert(0,a[i])
else:
  for i in range(0,s):
    if i%2!=0:
      b.append(a[i])
    if i%2==0:
      b.insert(0,a[i])  
print(" ".join(map(str,b)))

### FIXED CODE ###

s=int(input())
a=list(map(int,input().split()))
b=[]
if s%2!=0:
  for i in range(s-1,-1,-2):
    b.append(a[i])
  for i in range(1,s,2):
    b.append(a[i])
else:
  for i in range(s-1,0,-2):
    b.append(a[i])
  for i in range(0,s,2):
    b.append(a[i])
print(" ".join(map(str,b)))
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
*A, = map(int, input().split())
indices = {a: i for i, a in enumerate(A)}
seen_idx = [-1, N]
ans = 0
for a in range(1, N+1):
    idx = indices[a]
    t = bisect_left(seen_idx, idx)
    seen_idx = seen_idx[:t] + [idx] + seen_idx[t:]
    left = idx - seen_idx[t-1]
    right = seen_idx[t+1] - idx
    ans += left * right * a
print(ans)

### FIXED CODE ###

N = int(input())
*A, = map(int, input().split())
indices = {a: i for i, a in enumerate(A)}
left = {i: i for i in range(N)} # "left[i] = l" is equivalent to "A[l], ..., A[i-1] > A[i]"
right = {i: i for i in range(N)} # "right[i] = r" is equivalent to "A[i] < A[i+1], ..., A[r]"
ans = 0
for a in range(N, 0, -1):
    idx = indices[a]
    l, r = left[idx], right[idx]
    ans += (idx - l + 1) * (r - idx + 1) * a
    left[r+1], right[l-1] = l, r # A[l-1] < A[l], ..., A[r] > A[r+1]
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 10**10
for i in range(n):
    tmp = s[:i].count('W') + s[i+1:].count('E')
    if tmp < ans:
        ans = tmp
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
l = 0
r = s[1:].count('E')
ans = l + r

for i in range(1, n):
    if s[i-1] == 'W':
        l += 1
    if s[i] == 'E':
        r -= 1
    if l + r < ans:
        ans = l + r
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,D,A = map(int,readline().split())
mons = [list(map(int,readline().split())) for i in range(N)]
for i in range(N):
    mons[i][1] = (mons[i][1]+A-1)//A

mons.sort(key=lambda x: x[0])

ans = 0
for i in range(N):
    if mons[i][1] > 0:
        c = mons[i][1]
        mons[i][1] = 0
        ans += c
        for j in range(i+1,N):
            if mons[j][0] <= mons[i][0]+2*D:
                mons[j][1] -= c
            else:
                break

#print(mons)
print(ans)


### FIXED CODE ###

from collections import deque

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

mons.sort(key=lambda x: x[0])

damages = deque()
nowdmg = 0
ans = 0
for i in range(N):
    while len(damages) != 0:
        if mons[i][0] >= damages[0][0]+1:
            rec = damages.popleft()
            nowdmg += rec[1]
        else:
            break
    if mons[i][1]+nowdmg > 0:
        c = mons[i][1]+nowdmg
        ans += c
        damages.append([mons[i][0]+2*D,c])
        nowdmg -= c

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

N, M, Q = [int(_) for _ in input().split()]
train = [[]] * M
question = [[]] * Q
for i in range(M):
    train[i] = [int(_) for _ in input().split()]
for i in range(Q):
    question[i] = [int(_) for _ in input().split()]

l = []
for i in range(N):
    s = 0
    l2 = []
    for j in range(N):
        if i >= j:
            a = train.count([j+1, i+1])
        else:
            a = train.count([i+1, j+1])
        l2.append(s + a)
        s += a
    l.append(l2)

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if i == 0:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][i-1]
        ans += d
    print(ans)



### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]

l = [[0 for i in range(N+1)] for j in range(N+2)]
for t in [input().split() for _ in range(M)]:
    i = int(t[0])
    j = int(t[1])
    l[i][j] += 1

for k in range(N):
    for i in range(1, N-k+1):
        j = i + k
        l[i][j] += l[i][j-1] + l[i+1][j] - l[i+1][j-1]

for k in [input().split() for _ in range(Q)]:
    p = int(k[0])
    q = int(k[1])
    print(l[p][q])
### BUGGY CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[(i,j) for i in range(-2,3) for j in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for (i,j) in temp:
            nexty,nextx=y+i,x+j
            if 0<=nexty<h and 0<=nextx<w and s[nexty][nextx]>=0:
                dist=s[nexty][nextx]
                if i*i+j*j<=1 and dist>s1:
                    s[nexty][nextx]=s1
                    que.append([nexty,nextx])
                elif dist>s1+1:
                    s[nexty][nextx]=s1+1
                    que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()


### FIXED CODE ###

from collections import deque
from sys import stdin

def bfs():
    readline=stdin.readline
    h,w=map(int,readline().split())
    sy,sx=map(int,readline().split())
    gy,gx=map(int,readline().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(readline()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[i for i in range(-2,3)]
    while que:
        y,x=que.popleft()
        s1=s[y][x]
        for i in temp:
            nexty=y+i
            if 0<=nexty<h:
                s2=s[nexty]
                for j in temp:
                    nextx=x+j
                    if 0<=nextx<w and s2[nextx]>=0:
                        dist=s2[nextx]
                        if i*i+j*j<=1 and dist>s1:
                            s[nexty][nextx]=s1
                            que.appendleft([nexty,nextx])
                        elif dist>s1+1:
                            s[nexty][nextx]=s1+1
                            que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])
bfs()