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

import networkx as nx


def is_inside(x, y, W, H, G):
    return (x <= H-1 and y <= W-1 and
            x >= 0 and y >= 0 and
            G[x][y] != "#")


def main():
    graph = nx.Graph()
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    G = [list(input()) for _ in range(H)]
    seen = set()

    for h in range(H):
        for w in range(W):
            v = h * W + w
            if not is_inside(h, w, W, H, G):
                continue
            for step_h in range(-2, 3):
                for step_w in range(-2, 3):
                    h_, w_ = h+step_h, w+step_w
                    v_ = h_ * W + w_
                    if is_inside(h_, w_, W, H, G) and v_ not in seen:
                        if ((max(abs(step_h), abs(step_w)) == 1) and
                                (min(abs(step_h), abs(step_w)) == 0)):
                            graph.add_edge(v, v_, weight=0)

                        else:
                            graph.add_edge(v, v_, weight=1)
            seen.add(v)
    
    start = (Ch - 1) * W + (Cw - 1)
    end = (Dh - 1) * W + (Dw - 1)
    try:
        ans = nx.dijkstra_path_length(graph, start, end)
    except nx.NetworkXNoPath:
        ans = -1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def is_inside(x, y, W, H, G):
    return (x <= H-1 and y <= W-1 and
            x >= 0 and y >= 0 and
            G[x][y] != "#")


def main():
    H, W = map(int, input().split())
    Cx, Cy = map(int, input().split())
    Dx, Dy = map(int, input().split())

    G = [list(input()) for _ in range(H)]
    INF = int(1e9)
    q = deque()
    q.append((Cx-1, Cy-1, -INF, Cx-1, Cy-1))
    warps = [[INF] * W for _ in range(H)]
    while q:
        x, y, warp, prev_x, prev_y = q.popleft()

        if warps[x][y] != INF:
            continue

        num_warps = warps[prev_x][prev_y] + warp
        warps[x][y] = num_warps

        for step_x in range(-2, 3):
            for step_y in range(-2, 3):
                x_, y_ = x+step_x, y+step_y
                if is_inside(x_, y_, W, H, G) and warps[x_][y_] == INF:
                    if ((max(abs(step_x), abs(step_y)) == 1) and
                            (min(abs(step_x), abs(step_y)) == 0)):

                        q.appendleft((x_, y_, 0, x, y))
                    else:
                        q.append((x_, y_, 1, x, y))

    ans = warps[Dx-1][Dy-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


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

import math
import collections

def combinations_count(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


k = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
s = 0
for i in c.values():
  if i == 1:
    s += 0
    continue
  s += combinations_count(i, 2)

for i in a:
  j = c[i] - 1
  if j == 1:
    print(s - 1)
    continue
  elif j == 0:
    print(s)
    continue
  b = combinations_count(j, 2)
  y = combinations_count(c[i], 2)
  d = y - b
  print(s - d)

### FIXED CODE ###

import collections


k = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
s = 0
for i in c.values():
  s += i * (i - 1) / 2

for i in a:
  j = c[i] - 1
  b = j * (j - 1) // 2
  y = (j + 1) * j // 2
  d = y - b
  print(int(s - d))
### BUGGY CODE ###

from collections import deque
X = str(input())
lx = len(X)
st = deque([])

for i in range(lx):
  if X[i] == "S":
    st.append("S")
  else:
    if "S" in st:
      st.pop()
    else:
      st.appendleft("T")
      
print(len(st))

### FIXED CODE ###

X = str(input())
X = X.replace("ST","")
lx = len(X)
s_count = 0
t_count = 0
for i in range(lx):
  if X[i] == "S":
    s_count += 1
  else:
    if s_count:
      s_count -= 1
    else:
      t_count += 1
   
print(s_count + t_count)
### BUGGY CODE ###

import heapq
a, b = map(int, input().split())
c = list(map(int, input().split()))
heapq.heapify(c)
for i in range(b):
    d, e = map(int, input().split())
    for j in range(d):
        f = heapq.heappop(c)
        if f >= e:
            heapq.heappush(c, f)
            break
        else:
            heapq.heappush(c, e)
print(sum(c))


### FIXED CODE ###

import heapq
a, b = map(int, input().split())
c = list(map(int, input().split()))
heapq.heapify(c)
d = []
for i in range(b):
    e, f = map(int, input().split())
    d.append([e, f])
d = sorted(d, key=lambda x: x[1], reverse=True)
for i in range(len(d)):
    g = heapq.heappop(c)
    if d[i][1] < g:
        heapq.heappush(c, g)
        break
    else:
        heapq.heappush(c, g)
        for j in range(d[i][0]):
            g = heapq.heappop(c)
            if g < d[i][1]:
                heapq.heappush(c, d[i][1])
            else:
                heapq.heappush(c, g)
                break
print(sum(c))
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    # p = tuple(geta(lambda s: int(s.decode()[2:])))
    p = tuple(geta(float))

    cur = [0] * (N + 1)
    cur[0] = 1

    for i, pi in enumerate(p, 1):
        upd = [0] * (N + 1)
        qi = 1 - pi

        upd[0] = cur[0] * qi
        for j in range(1, i + 1):
            upd[j] = cur[j - 1] * pi + cur[j] * qi
        cur = upd

    print(sum(cur[N // 2 + 1:]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    # p = tuple(geta(lambda s: int(s.decode()[2:])))
    p = tuple(geta(float))

    dp = [[0] * (i + 2) for i in range(N + 1)]
    dp[0][0] = 1

    for i, pi in enumerate(p, 1):
        qi = 1 - pi
        dpi = dp[i]
        dpi1 = dp[i - 1]

        dpi[0] = dpi1[0] * qi

        for j in range(1, i + 1):
            dpi[j] = dpi1[j - 1] * pi + dpi1[j] * qi

    print(sum(dp[N][N // 2 + 1:]))


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

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

total=0
for i in range(1,N+1):
    A=P[:i]
    B=sorted(A)
    if B[0]==A[i-1]:
        total+=1
print(total)

### FIXED CODE ###

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

total=1
minP=P[0]
for i in range(1,N):
    if P[i]<minP:
        total+=1
        minP=P[i]
print(total)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def lcm_list(A):
    l = A[0]
    for a in A[1:]:
        l = lcm(l, a)
    return l

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=1
for i in l:
    ans*=i

if ans>1000000000000000000:print(-1)
else:print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
if l[0]==0:
    print(0)
    exit(0)
ans=1
for i in l:
    ans*=i
    if ans>1000000000000000000:
        print(-1)
        exit(0)
print(ans)
### BUGGY CODE ###

N=int(input())
# https://qiita.com/drken/items/97e37dd6143e33a64c8c#3-%E3%82%81%E3%81%90%E3%82%8B%E5%BC%8F%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%81%95%E3%82%89%E3%81%AA%E3%82%8B%E5%88%A9%E7%82%B9
print(0,flush=True)
s=str(input())
temp=s
tempway='right'
templind=0

l=0
def is_ok():
    if temp==s and (mid-templind)%2==1:
        if tempway=='right':
            return True
        else: return False
    elif temp!=s and (mid-tmeplind)%2==0:
        if tempway=='right':
            return False
        else: return True
    else:
        exit()


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """
    global ng
    global ok
    global mid
    global tempway

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため
    tempway='left'
    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        print(mid,flush=True)
        s=str(input())
        if is_ok():
            ok = mid
            tempway='left'
        else:
            ng = mid
            templind=mid
            tempway='right'
bin_search_meguru()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

def bfs(branch,n):
	arrival = [0 for i in range(n+1)]
	q = [1]
	arrival[q[0]] = 1
	while len(q) >= 1:
		for k in range(len(branch[q[0]])):
			if arrival[branch[q[0]][k]] == 0:
				arrival[branch[q[0]][k]] = arrival[q[0]] + 1
				q.append(branch[q[0]][k])
		q.pop(0)
	return arrival

n,m = map(int,input().split())
branch = dict()
for i in range(n):
	branch[i+1] = []
for i in range(m):
	a,b = map(int,input().split())
	branch[a].append(b)
	branch[b].append(a)

arrival = bfs(branch,n)
if arrival[n]-arrival[1] == 2:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
branch = dict()
for i in range(n):
	branch[i+1] = []
for i in range(m):
	a,b = map(int,input().split())
	branch[a].append(b)
	branch[b].append(a)

q = []
for i in range(len(branch[1])):
	q.append(branch[1][i])

check = False
for i in range(len(q)):
	if n in branch[q[i]]:
		check = True
		break
if check:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

import copy
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    m = 80**2 + 10
    dp = [[False]*(m+1) for _ in range(w)]
    dp[0][abs(a[0][0] - b[0][0])] = True
    for i in range(1, w):
        x = abs(a[0][i] - b[0][i])
        for j in range(m+1):
            if dp[i-1][j]:
                if j+x <= m:
                    dp[i][j+x] = True
                dp[i][abs(j-x)] = True
    for i in range(1, h):
        for j in range(w):
            buf = [False]*(m+1)
            x = abs(a[i][j] - b[i][j])
            for k in range(m+1):
                f = False
                if j == 0:
                    if dp[0][k]:
                        f = True
                else:
                    if dp[j-1][k] or dp[j][k]:
                        f = True
                if f:
                    if k+x <= m:
                        buf[k+x] = True
                    buf[abs(k-x)] = True
            dp[j] = copy.deepcopy(buf)
    for i in range(m+1):
        if dp[w-1][i]:
            print(i)
            break

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

x = int(input())
i, pos = 0, set([0])

while True:
    inner = False
    new_pos = set()
    for p in pos:
        if p + i == x or p - i == x:
            inner = True
            break
        new_pos.add(p)
        new_pos.add(p + i)
        new_pos.add(p - i)

    if inner:
        print(i)
        break

    pos = new_pos
    i += 1


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

x = int(input())


total = 0
for i in range(x + 1):
    total += i
    if total >= x:
        print(i)
        break
### BUGGY CODE ###

from bisect import bisect_left
def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	trains.sort()	
	frms = [x[0] for x in trains]
	tos = [x[1] for x in trains]

	for query in queries:
		start = bisect_left(frms, query[0])
		tos_tmp = tos[start:]
		tos_tmp.sort()
		ans = bisect_left(tos_tmp, query[1] + 1)
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + (cmt[i - 1][j] - cmt[i - 1][j - 1]) + xmt[i][j] 
	
	for query in queries:
		i, j = query
		ans = cmt[j][j] - cmt[i - 1][j] - cmt[j][i - 1] + cmt[i - 1][i - 1]
		print(ans)

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

n = int(input())

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


total = 0
for i in range(n-1):
    for j in a[i+1:]:
        total += (a[i]*j)%(10**9+7)
        total = total%(10**9+7)

print(total)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 
 
print(ans % mod)
### BUGGY CODE ###

from collections import deque

def BFS(maze,h,w,s,g,k): 
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    (x,y) = s
    (gx,gy) = g
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or maze[nx][ny] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    return d[gx][gy]

def main():
    h,w,k = map(int,input().split())
    x1,y1,x2,y2 = map(int,input().split())
    x1 -= 1
    x2 -= 1
    y1 -= 1
    y2 -= 1
    c = [list(input()) for _ in range(h)]
    print(BFS(c,h,w,[x1,y1],[x2,y2],k))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools

N = int(input())
A = {}
for i in range(N):
    S = list(input())
    S.sort()
    S = ''.join(S)
    A[S] = A.get(S, 0) + 1

ans = 0
for i in A.values():
    if i > 1:
        iL = [j for j in range(i)]
        ans += len(list(itertools.combinations(iL, 2)))
        
print(ans)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
    S = list(input())
    S.sort()
    S = ''.join(S)
    A[S] = A.get(S, 0) + 1

ans = 0
for i in A.values():
    if i > 1:
        iL = [j for j in range(i)]
        ans += sum(iL)
    
print(ans)
### BUGGY CODE ###

def resolve():
    n = int(input())
    dict = {}
    for i in range(n):
        s = input()
        s = sorted(s)
        s = "".join(s)
        if s in dict.keys():
            dict[s] += 1
        else:
            dict[s] =1
    ans = 0
    for i in dict.keys():

        ct = dict[i]
        ans += (ct*(ct-1))//2
    print(ans)

resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    s = [",".join(sorted(input())) for i in range(n)]
    ans = {}
    count = 0
    for i in range(n):
        if s[i] in ans:
            count += ans[s[i]]
            ans[s[i]] += 1
        else:
            ans[s[i]] = 1
    print(count)
resolve()
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

from collections import  deque
seen = set()
queue = deque([(0, CH-1, CW-1)])

while queue:
    move, row, col = queue.popleft()

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)