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

import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter
import copy


def calcstep(maze, s, g):
    h, w = len(maze), len(maze[0])
    maze[s[0]] = maze[s[0]][:s[1]] + 's' + maze[s[0]][s[1]+1:]
    maze[g[0]] = maze[g[0]][:g[1]] + 'g' + maze[g[0]][g[1]+1:]
    
    cost = np.zeros((h, w), dtype=int) + 999
    done = np.zeros((h, w), dtype=bool)
    barrier = np.zeros((h, w), dtype=bool)

    g = np.array([[0, 1, 0],
                  [1, 1, 1],
                  [0, 1, 0]])

    for i in range(h):
        maze[i] = list(maze[i])
        for j in range(w):
            if maze[i][j] == 's':
                start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if maze[i][j] == 'g':
                goal = (i, j)
            if maze[i][j] == '#':
                barrier[i, j] = True

    for i in range(1, 999):

        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1
        cost[done_next] = cost_next[done_next]
        cost[barrier] = 999
        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            break
    return i



h, w = map(int, input().split())
maze = [input() for _ in range(h)]


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        
        for k in range(h):
            for l in range(w):
                if(maze[k][l] == '#'): continue
                if(i==k and j==l): continue
                tmpmaze = copy.deepcopy(maze)
                steps = calcstep(tmpmaze, [i, j], [k, l])
                if(steps > res):
                    res = steps
print(res)

### FIXED CODE ###

from collections import deque
import copy

def bfs(grid, start):
    H, W = len(grid), len(grid[0])
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
 
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))

h, w = map(int, input().split())
maze = [input() for _ in range(h)]


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        tmpmaze = copy.deepcopy(maze)
        steps = bfs(tmpmaze, [i, j])
        if(steps > res):
            res = steps
print(res)
### BUGGY CODE ###

def main():
    S = input()
    N = int(input())
    for i in range(N):
        Q = [i for i in input().split()]
        if len(Q) == 1:
            S = ''.join(list(reversed(S)))
        else:
            F = int(Q[1])
            C = Q[2]
            if F == 1:
                S = '{}{}'.format(C, S)
            else:
                S = '{}{}'.format(S, C)
    print(S)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def RevFlag(flag):
    if flag:
        return False
    else:
        return True

def main():
    from collections import deque
    S = input()
    d = deque()
    for s in S:
        d.append(s)
    N = int(input())
    rev = False

    for i in range(N):
        Q = [i for i in input().split()]
        if len(Q) == 1:
            rev = RevFlag(rev)
        else:
            F = int(Q[1])
            C = Q[2]
            if F == 1:
                if rev:
                    d.append(C)  # 末尾
                else:
                    d.appendleft(C)  # 先頭
            else:
                if rev:
                    d.appendleft(C)  # 先頭
                else:
                    d.append(C)  # 末尾
    if rev:
        d = ''.join(list(reversed(d)))
    else:
        d = ''.join(list(d))
    print(d)


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

N, K = map(int, input().split())
arr = []
for i in range(N):
  a, b = map(int, input().split())
  arr += [a]*b

arr.sort()
print(arr[K-1])

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [0]*100001
S = set()
for i in range(N):
  a, b = map(int, input().split())
  cnt[a-1] += b
  S.add(a)

acc = 0
for s in sorted(S):
  acc += cnt[s-1]
  if acc >= K:
    print(s)
    break
### BUGGY CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
dis = [[None]*N for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append(R)
    graph[R].append(L)
    dis[L][R] = D
    dis[R][L] = (-1)*D

data = [None]*N
det = 0

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y] == None:
                data[y] = data[x] + dis[x][y]
                stack.append(y)
            else:
                if data[y] - data[x] != dis[x][y]:
                    det = -1
                    break
    if det == -1:
        break

if det == 0:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

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

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

graph = [[] for i in range(N)]

for i in range(M):
    L,R,D = map(int,input().split())
    L -= 1
    R -= 1
    graph[L].append([R,D])
    graph[R].append([L,-D])
    
data = [None]*N

for i in range(N):
    if data[i] != None:
        continue
    data[i] = 0
    stack = deque()
    stack.append(i)
    while stack:
        x = stack.popleft()
        for y in graph[x]:
            if data[y[0]] == None:
                data[y[0]] = data[x] + y[1]
                stack.append(y[0])
            else:
                if data[y[0]] - data[x] != y[1]:
                    print("No")
                    sys.exit()
    
print("Yes")
### BUGGY CODE ###

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

dp = [0 for _ in range(n)]
for i in range(1, n):
    dp[i] = min([dp[j] + abs(h[j] - h[i]) for j in range(max(0, i-k), i)])

print(dp[n-1])

### FIXED CODE ###

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

dp = [0 for _ in range(n)]
for i in range(1, n):
    dp[i] = min([dp[j] + abs(h[j] - h[i]) for j in range(max(0, i-k), i)])

print(dp[n-1])
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab0 = []
abn = []
res="IMPOSSIBLE"
for x in ab:
    if x[0] == 0:
        if x[1] in abn:
            res= "POSSIBLE"
            break
        ab0.append(x[1])
    if x[1] == n-1:
        if x[0] in ab0:
            res= "POSSIBLE"
            break
        abn.append(x[0])

print(res)



### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import functools
import operator

n = int(input())
li = [int(i) for i in input().split()]
result = functools.reduce(operator.mul, li)

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

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
the = pow(10,18)
ans = 1

if 0 in A:
    print(0)
else:
    for i in range(n):
        ans *= A[i]
        if ans >the:
            print(-1)
            break
        else:
            continue
    if ans <= the:
        print(ans)
### BUGGY CODE ###

S = input()
dp = [1, 0, 0, 0]
for s in S:
    tmp = [0, 0, 0, 0]
    if s == 'A' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[1] += dp[0]
    if s == 'B' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[2] += dp[1]
    if s == 'C' or s == '?':
        tmp[0] += dp[0]
        tmp[1] += dp[1]
        tmp[2] += dp[2]
        tmp[3] += dp[3]
        tmp[3] += dp[2]
    dp = tmp
print(dp[-1]%(10**9+7))

### FIXED CODE ###

def main():
    S = input()
    mod = 10**9+7
    dp0 = 1
    dp1 = 0
    dp2 = 0
    dp3 = 0

    for s in S:
        tmp0 = dp0
        tmp1 = dp1
        tmp2 = dp2
        tmp3 = dp3

        if s == '?':
            tmp0 += 2*dp0 % mod
            tmp1 += (2*dp1 + dp0) % mod
            tmp2 += (2*dp2 + dp1) % mod
            tmp3 += (2*dp3 + dp2) % mod
        elif s == 'A':
            tmp1 += dp0 % mod
        elif s == 'B':
            tmp2 += dp1 % mod
        elif s == 'C':
            tmp3 += dp2 % mod
        dp0 = tmp0
        dp1 = tmp1
        dp2 = tmp2
        dp3 = tmp3

    print(dp3%(mod))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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


A = []
for i in range(N):
  if S[i] == "W":
    A.append(1)
  elif S[i] == "E":
    A.append(-1)
    
saidai = 0
for i in range(N):
  if saidai < sum(A[i+1:]) - sum(A[:i]):
    
    saidai = sum(A[i+1:]) - sum(A[:i])
    flag = i
    
ans = A[:flag].count(1) + A[flag+1:].count(-1)

print(ans)
  



### FIXED CODE ###

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


A = []
for i in range(N):
  if S[i] == "W":
    A.append(1)
  elif S[i] == "E":
    A.append(-1)
    
R = [A[0]]
for i in range(1,N):
  R.append(R[-1] + A[i])


saidai = 0
for i in range(N):
  if i == 0:
    if saidai < R[N-1] - R[0]:
      saidai = R[N-1] - R[0]
      flag = i
  elif i == N-1:
    if saidai < -R[N-2]:
        saidai = -R[N-2]
        flag = i
  else:
    if saidai < (R[N-1] - R[i]) - R[i-1]:
        saidai = (R[N-1] - R[i]) - R[i-1]
        flag = i  
    
ans = A[:flag].count(1) + A[flag+1:].count(-1)

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

_input = int(input())

power = 1

for i in range(1, _input + 1):
  power *= i

power %= 1000000007

print(power)

### FIXED CODE ###

_input = int(input())

power = 1

for i in range(1, _input + 1):
  if power >= 1000000007:
    power %= 1000000007
  power *= i

power %= 1000000007

print(power)
### BUGGY CODE ###

n = int(input())
s = input()
char = ""
count = 0

for i in range(len(s)):
    for j in range(i + 1, len(s)):
        if s[j] != s[i]:

            if s[i] == "R":
               if s[j] == "G": char = "B"
               else: char = "G"
            elif s[i] == "G":
                if s[j] == "R": char = "B"
                else: char = "R"
            else:   # s[i] は B
                if s[j] == "G": char = "R"
                else: char = "G"
            a = j - i

            for k in range(j + 1, len(s)):     
                if s[k] == char and a != k - j:
                    count += 1
print(count)

### FIXED CODE ###

import math

n = int(input())
s = input()
count = 0

rCount = s.count("R")
gCount = s.count("G")
bCount = s.count("B")
ans = rCount * gCount * bCount

for dis in range(1, math.ceil(len(s) / 2)):
    for i in range(dis, len(s) - dis):
        if s[i-dis] != s[i] and s[i-dis] != s[i+dis] and s[i] != s[i+dis]:
            ans -= 1
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
an,ans=[],[]
for num in lisb:
    for nu in lisa:an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):print(ans[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

R, C, K = map(int, input().split())
score = [[0]*C for i in range(R)]

for i in range(K):
  r, c, v = map(int, input().split())
  score[r-1][c-1]+=v
  
ans = [[[0]*4 for i in range(C)] for j in range(R)]
ans[0][0][1]=score[0][0]
ans[0][0][2]=score[0][0]
ans[0][0][3]=score[0][0]

for i in range(R):
  for j in range(C):
    if i>0:
      ans[i][j][0]=max(ans[i][j][0],ans[i-1][j][3])
      ans[i][j][1]=max(ans[i][j][1],ans[i-1][j][3]+score[i][j])
      ans[i][j][2]=max(ans[i][j][2],ans[i-1][j][3]+score[i][j])
      ans[i][j][3]=max(ans[i][j][3],ans[i-1][j][3]+score[i][j])
    if j>0:
      ans[i][j][0]=max(ans[i][j][0],ans[i][j-1][0])
      ans[i][j][1]=max(ans[i][j][1],ans[i][j-1][0]+score[i][j],ans[i][j-1][1])
      ans[i][j][2]=max(ans[i][j][2],ans[i][j-1][1]+score[i][j],ans[i][j-1][2])
      ans[i][j][3]=max(ans[i][j][3],ans[i][j-1][2]+score[i][j],ans[i][j-1][3])

print(ans[R-1][C-1][3])

### FIXED CODE ###

R, C, K = map(int, input().split())
score = [[0]*C for i in range(R)]

for i in range(K):
  r, c, v = map(int, input().split())
  score[r-1][c-1]+=v
  
ans0 = [[0]*C for i in range(R)]
ans1 = [[0]*C for i in range(R)]
ans2 = [[0]*C for i in range(R)]
ans3 = [[0]*C for i in range(R)]

ans1[0][0]=score[0][0]
ans2[0][0]=score[0][0]
ans3[0][0]=score[0][0]

for i in range(R):
  for j in range(C):
    if i>0:
      ans0[i][j]=max(ans0[i][j],ans3[i-1][j])
      ans1[i][j]=max(ans1[i][j],ans3[i-1][j]+score[i][j])
      ans2[i][j]=max(ans2[i][j],ans3[i-1][j]+score[i][j])
      ans3[i][j]=max(ans3[i][j],ans3[i-1][j]+score[i][j])
    if j>0:
      ans0[i][j]=max(ans0[i][j],ans0[i][j-1])
      ans1[i][j]=max(ans1[i][j],ans0[i][j-1]+score[i][j],ans1[i][j-1])
      ans2[i][j]=max(ans2[i][j],ans1[i][j-1]+score[i][j],ans2[i][j-1])
      ans3[i][j]=max(ans3[i][j],ans2[i][j-1]+score[i][j],ans3[i][j-1])

print(ans3[R-1][C-1])
### BUGGY CODE ###

a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))

### FIXED CODE ###

a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
        i+=1
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

white = 0
maze = [['#']*(W+2)]
for i in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#']*(W+2))

def check(x,y,n):
	if x==W and y==H:
		print(white-n)
		sys.exit()
	elif maze[y][x] == '.':
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])
	else:
		return

q = queue.Queue()
q.put([1,1,1])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)


### FIXED CODE ###

import sys
import queue

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


white = 0
	
maze = []

for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

if maze[0][0] == '#' or maze[H-1][W-1] == '#':
	print (-1)
	sys.exit()

	
maze[H-1][W-1] =	'g'
	
q = queue.Queue()
q.put([0,0,0])

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if maze[y][x] == 'g':
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)
	
print(-1)
### BUGGY CODE ###

from queue import Queue

def bfs(AB,N):
    S = [None for _ in range(N+1)]
    #S[i]:部屋iにつけるべきサイン
    q = Queue()
    q.put(1)

    while not q.empty():
        p = q.get()
        for i in range(1,N+1):
            if (p,i) in AB and S[i] == None:
                q.put(i)
                S[i] = p

    can = True
    for i in range(2,N+1):
        if S[i] == None:
            can = False

    if can:
        return S[2:]
    else:
        return -1

def main():
    N,M = map(int,input().split())
    AB = [tuple(map(int,input().split())) for _ in range(M)]

    AB_ = set(AB)
    for i in range(M):
        AB_.add((AB[i][1],AB[i][0]))
    AB = AB_

    ans = bfs(AB,N)
    if ans == -1:
        print("No")
    else:
        print("Yes")
        for i in range(len(ans)):
            print(ans[i])

if __name__ == "__main__":
    main()


### FIXED CODE ###

from queue import Queue

def bfs(AB,N):
    S = [None for _ in range(N+1)]
    #S[i]:部屋iにつけるべきサイン
    AB_N = [set() for _ in range(N+1)]
    for ab in AB:
        a,b = ab[0],ab[1]
        AB_N[a].add((a,b))

    q = Queue()
    q.put(1)

    while not q.empty():
        p = q.get()
        for ab in AB_N[p]:
            a,b = ab[0],ab[1]
            if a == p:
                if  S[b] == None:
                    q.put(b)
                    S[b] = p

    can = True
    for i in range(2,N+1):
        if S[i] == None:
            can = False

    if can:
        return S[2:]
    else:
        return -1

def main():
    N,M = map(int,input().split())
    AB = [tuple(map(int,input().split())) for _ in range(M)]

    AB_ = set(AB)
    for i in range(M):
        AB_.add((AB[i][1],AB[i][0]))
    AB = AB_

    ans = bfs(AB,N)
    if ans == -1:
        print("No")
    else:
        print("Yes")
        for i in range(len(ans)):
            print(ans[i])

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

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1 for _ in range(n)]
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for i in range(M)][::-1]

ans = [comb2(N)]
uf = UnionFind(N+1)
for i in range(M-1):
  a,b=edges[i]
  uf.unite(a,b)
  connected=0
  for g in uf.g:
    connected += comb2(uf.size(g))
  ans.append(ans[0]-connected)

ans = ans[::-1]
for i in range(M):
  print(ans[i])

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
E = [tuple(map(int,input().split())) for _ in range(M)]

total=comb2(N)
uf = UnionFind(N+1)
ans = [total]
for i in range(M-1):
  a,b = E[-i-1]
  if uf.same(a,b):
    ans.append(ans[-1])
    continue
  else:
    size1,size2 = uf.size(a),uf.size(b)
    uf.unite(a,b)
    size3 = uf.size(a)
    tmp = ans[-1]+comb2(size1)+comb2(size2)-comb2(size3)
    ans.append(tmp)
print(*ans[::-1])
### BUGGY CODE ###

import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,w=mp()
item=[lmp() for i in range(n)]
dp=[[0]*(w+1) for i in range(n+1)]
for i in range(n):
    for k in range(1,w+1):
        if k<item[i][0]:
            dp[i+1][k]=dp[i][k]
        else:
            dp[i+1][k]=max(dp[i][k],dp[i][k-item[i][0]]+item[i][1])
print(dp[-1][-1])

### FIXED CODE ###

import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,w=mp()
dp=[0]*(w+1)
for i in range(n):
    x,y=mp()
    for k in range(w,x-1,-1):
        dp[k]=max(dp[k],dp[k-x]+y)
print(dp[-1])
### BUGGY CODE ###

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    
    
    s = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input()[:-1] + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))
    
    
    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    not_yet = deque([(ch, cw)])
    one_time = deque([])
    
    while len(not_yet) > 0:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        for (p, q) in move:
            if ans[x+p][y+q] == -1:
                not_yet.append((x+p, y+q))
                ans[x+p][y+q] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.popleft()
                for i in range(x2-2, x2+3):
                    for j in range(y2-2, y2+3):
                        if ans[i][j] == -1:
                            ans[i][j] = ans[x2][y2]+1
                            not_yet.append((i, j))
          
    print(ans[dh][dw])
    
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    s = [input().replace("\n", "") for _ in range(h)]
    
    ans = [[-1]*w for _ in range(h)]
    ans[ch-1][cw-1] = 0
    not_yet = deque([(ch-1, cw-1)])
    one_time = deque([])
    while not_yet:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        if x > 0 and ans[x-1][y] == -1 and s[x-1][y] == ".":
            not_yet.append((x-1, y))
            ans[x-1][y] = ans[x][y]
        if x < h-1 and ans[x+1][y] == -1 and s[x+1][y] == ".":
            not_yet.append((x+1, y))
            ans[x+1][y] = ans[x][y]
        if y > 0 and ans[x][y-1] == -1 and s[x][y-1] == ".":
            not_yet.append((x, y-1))
            ans[x][y-1] = ans[x][y]
        if y < w-1 and ans[x][y+1] == -1 and s[x][y+1] == ".":
            not_yet.append((x, y+1))
            ans[x][y+1] = ans[x][y]
        if not not_yet:
            while one_time:
                x2, y2 = one_time.popleft()
                for i in range(max(0, x2-2), min(h, x2+3)):
                    for j in range(max(0, y2-2), min(w, y2+3)):
                        if ans[i][j] == -1 and s[i][j] == ".":
                            ans[i][j] = ans[x][y]+1
                            not_yet.append((i, j))

    print(ans[dh-1][dw-1])
            
            
            
        
    
    
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
ans=0
for i in range(k+1):
  for j in range(k+1):
    for k in range(k+1):
      ans=i+j+k
      if ans==s:
        cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
print(sum(0<=s-x-y<=k for x in range(k+1) for y in range(k+1)))
#コピペです。