Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import math
import bisect
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

def isOK(index,key):
    if l[index] <= key:
        return True
    else:
        return False

def binary_search(key):
    left=len(l)-1
    right=-1
    
    while abs(right - left) >1:
        mid=(right+left)//2
        
        if isOK:
            right=mid
        else:
            left=mid
    return right

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

primes=callIsPrime(10**5)
l=[]

for i in range(len(primes)):
    if (primes[i]+1)//2 in primes:
        l.append(primes[i])
        
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    L=bisect.bisect_left(l,L)
    R=bisect.bisect_right(l,R)
    
    print(R-L)
    
    


    



Fixed submission:
# coding: utf-8
import math
import bisect
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

def isOK(index,key):
    if l[index] <= key:
        return True
    else:
        return False

def binary_search(key):
    left=len(l)-1
    right=-1
    
    while abs(right - left) >1:
        mid=(right+left)//2
        
        if isOK:
            right=mid
        else:
            left=mid
    return right

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

primes=callIsPrime(10**5)
l=[]

for i in range(len(primes)):
    if (primes[i]+1)//2 in primes:
        l.append(primes[i])
        
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    L=bisect.bisect_left(l,L)
    R=bisect.bisect_right(l,R)
    
    print(R-L)
Buggy python submission (verdict: Runtime Error):
n=int(input())
l=list(map(int,input().split(" ")))
ans=0

while i <len(l):
    if l[i]%2!=0:
        break
    else:
        l[i]=int(l[i]/2)
        i+=1
    ans+=1
print(ans)

Fixed submission:
n=int(input())
l=list(map(int,input().split(" ")))
ans=0
j=0
while j==0:
    i=0
    while i <len(l):
        if l[i]%2!=0:
            j=1
        else:
            l[i]=int(l[i]/2)
        i+=1
    ans+=1
print(ans-1)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
S=list(input())
T=list(input())

S.reverse()
T.reverse()

for i in range(len(S)-len(T)):
    flg=True
    for j in range(len(T)):
        if not(S[i+j]=="?"):
            if S[i+j]!=T[j]:
                flg=False
    if flg:
        for k in range(len(T)):
            S[i+k]=T[k]
        break    
        

S.reverse()

for i in range(len(S)):
    if S[i]=="?":
        S[i]="a"
if flg:
    print("".join(S))
else:
    print("UNRESTORABLE")



Fixed submission:
# coding: utf-8
S=list(input())
T=list(input())
flg=False
S.reverse()
T.reverse()

for i in range(max(0,len(S)-len(T)+1)):
    flg=True
    for j in range(len(T)):
        if not(S[i+j]=="?"):
            if S[i+j]!=T[j]:
                flg=False
    if flg:
        for k in range(len(T)):
            S[i+k]=T[k]
        break    
        

S.reverse()

for i in range(len(S)):
    if S[i]=="?":
        S[i]="a"
if flg:
    print("".join(S))
else:
    print("UNRESTORABLE")
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

N=int(input())
ans=lcm(1,int(input()))

for i in range(N-1):
    ans=lcm(ans,int(input()))

print(ans)

Fixed submission:
# coding: utf-8
import fractions as math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

N=int(input())
ans=lcm(1,int(input()))

for i in range(N-1):
    ans=lcm(ans,int(input()))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
N,M=map(int,input().split())
G=[[] for i in range(N+1)]

for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

flg=False

near=[]

for i in range(len(G[1])):
    near.append(G[1][i])

for i in range(len(G[N])):
    if G[N][i] in near:
        flg=True

if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Fixed submission:
# coding: utf-8
N,M=map(int,input().split())
G=[[] for i in range(N+1)]

for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

flg=False

near=[False for i in range(N+1)]

for i in range(len(G[1])):
    near[G[1][i]]=True

for i in range(len(G[N])):
    if near[G[N][i]]:
        flg=True

if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
b=[]
for i in range(n):
    if i%2==0:
        b.append("{}".format(A[i]))
    else:
        b.insert(0,"{}".format(A[i]))

if n%2==1:
    b.reverse()
    print(" ".join(b))
else:
    print(" ".join(b))



Fixed submission:
# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
l=[]
r=[]
k=1
for i in range(n):
    if i%2==0:
        r.append("{}".format(A[i]))
    else:
        l.append("{}".format(A[i]))
l.reverse()

b=l+r

if n%2==1:
    b.reverse()

print(" ".join(b))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
N,M=map(int,input().split())
picN=[]
picM=[]

for i in range(N):
    L=list(input())
    picN.append(L)

for i in range(M):
    L=list(input())
    picM.append(L)

K=N-M

for i in range(K):
    for j in range(K):
        flg=True
        for a in range(M):
            for b in range(M):
                if picN[a+i][b+j]!=picM[a][b]:
                    flg=False
        if flg:
            break
if flg:
    print("YES")
else:
    print("NO")

Fixed submission:
N,M = map(int,input().split())

A=[]
B=[]

for i in range(N):
    A.append(list(input()))
    
for i in range(M):
    B.append(list(input()))

k=N-M+1
ans=False

for i in range(k):
    for j in range(k):
        flg=True
        
        for p in range(M):
            for q in range(M):
                if A[i+p][j+q] != B[p][q]:
                    flg=False
                    
        ans=flg
        if ans:
            break
    if ans:
        break

if ans:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
st=input()
j="0"
u="0"
for i in st:
    if i=="d" and u=="0":
        u="d"
        j="1"
    elif i=="r" and u=="d":
        u="r1"
    elif i=="e" and u=="r1":
        u="e1"
    elif i=="a" and u=="e1":
        u="a1"
    elif i=="m" and u=="a1":
        u="0"
    elif i=="e" and u=="0":
        u="e2"
        j="2"
    elif i=="r" and u=="e2":
        u="0"
    """"""    
    elif i=="e" and u=="0":
        u="e3"
        j="0"
    elif i=="r" and u=="e3":
        u="r2"
    """"""
    elif i=="a" and u=="0" and j=="2":
        u="a2"
    elif i=="s" and u=="a2":
        u="s"
    elif i=="e" and u=="s":
        u="0"
        j="3"
    elif i=="r" and j=="3":
        j="0"
    else:
        print("NO")
        exit(0)
if u=="0":
    print("YES")
else:
    print("NO")

Fixed submission:
st=input()
c="0"
j="0"
u="0"
for i in st:
    if i=="d" and u=="0" and c=="0":
        u="d"
        j="1"
    elif i=="r" and u=="d":
        u="r1"
    elif i=="e" and u=="r1":
        u="e1"
    elif i=="a" and u=="e1":
        u="a1"
    elif i=="m" and u=="a1":
        u="0"
        
    elif i=="e" and u=="0" and c=="0":
        u="e2"
        if j !="1":
            c="1"
    elif i=="r" and u=="e2":
        u="0"
        j="2"
    elif i=="a" and u=="0" and j=="2":
        u="a2"
    elif i=="s" and u=="a2":
        u="s"
    elif i=="e" and u=="s":
        u="0"
        c="0"
        j="3"
    elif i=="r" and u=="0" and j=="3":
        j="0"
    else:
        print("NO")
        exit(0)
if u=="0"and c=="0":
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(n):
    for j in range(i + 1, n):
        s += a[i] * a[j]
        s %= 1000000007
print(s % 1000000007)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
s1 = sum(a)
s2 = 0
ans = 0
for i in range(n - 1):
    s2 += a[i]
    ans += a[i] * (s1 - s2)
print(ans % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
n=input()
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:
  print(-1)
else:
  print(ans)

Fixed submission:
import sys

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


def multiple(l):
    ans = 1
    if 0 in l:
        return 0
    for i in l:
        if ans * i > 10 ** 18:
            return -1
        else:
            ans *= i
    return ans


print(multiple(a))
Buggy python submission (verdict: Runtime Error):
t = input()
o = ""
for i in range(len(t)):
    if t[i] == "?":
        if i != 0 and t[i - 1] == "P":
            o += "D"
        elif i != len(t) and t[i + 1] == "D":
            o += "P"
        else:
            o += "D"
    else:
        o += t[i]

print(o)

Fixed submission:
print(input().replace('?','D'))

Buggy python submission (verdict: Runtime Error):
t = input()
o = ""
for i in range(len(t)):
    if t[i] == "?":
        if t[i - 1] == "P":
            o += "D"
        elif i != len(t):
            if t[i + 1] == "D":
                o += "P"
        else:
            o += "D"
    else:
        o += t[i]

print(o)

Fixed submission:
print(input().replace('?','D'))

Buggy python submission (verdict: Runtime Error):
t = input()
o = ""
for i in range(len(t)):
    if t[i] == "?":
        if t[i - 1] == "P":
            o += "D"
        elif t[i + 1] == "D":
            o += "P"
        else:
            o += "D"
    else:
        o += t[i]

print(o)

Fixed submission:
print(input().replace('?','D'))
Buggy python submission (verdict: Time Limit Exceeded):
a=list(map(int,input().split()))
m=0
for i in range(a[3]):
    if a[0]>0:
        m+=1
        a[0]-=1
    elif a[1]>0:
        a[1]-=1
    elif a[2]>0:
        m-=1
        a[2]-=1

print(m)

Fixed submission:
s=list(map(int,input().split()))
a=s[0]
b=s[1]
c=s[2]
k=s[3]
m=0

if k>a:
    m+=a
    k-=a
    if k>b:
        k-=b
        if k>c:
            m-=c
        else:
            m-=k
else:
    m=k


print(m)
Buggy python submission (verdict: Runtime Error):
s=input()
if s=="AAA" or s="BBB":
  print('No')
else:
  print('Yes')

Fixed submission:
s=input()
if s=="AAA" or s=="BBB":
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input())
if (a!=b and b!=c and c!=a) or (a==b and b==c):
  print('No')
else:
  print('Yes')


Fixed submission:
a,b,c=map(int,input().split())
if (a!=b and b!=c and c!=a) or (a==b and b==c):
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Runtime Error):
print(chr(ord(input()+1)

Fixed submission:
c=input()
print(chr(ord(c)+1))
Buggy python submission (verdict: Time Limit Exceeded):
from numba import njit

@njit
def factorize1(n):
    ans=dict()
    i = 2
    while i*i<=n:
        while n%i==0:
            n=n//i
            if i in ans:
                ans[i]+=1
            else:
                ans[i]=1
        i+=1
    if n!=1:
        ans[n]=1
        
    div=1
    for j in ans.items():
        div *= j[1]+1
    return div
   
N=int(input())
ans=1
for k in range(2,N):
    ans += factorize1(k)
print(ans)

Fixed submission:
N=int(input())
ans = 0
for i in range(1,N):
    ans += (N-1)//i
print(ans)
Buggy python submission (verdict: Runtime Error):
N,X,M=map(int,input().split())
A = [X,]
setA = {A,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if alast==0:
    print(sum(C))
elif (flag==False) and (alast!=0):
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Fixed submission:
N,X,M=map(int,input().split())
A = [X,]
setA = {X,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if flag:
    if alast==0:
        ans = sum(A)
    else:
        res = (N-d)%len(C)
        ans = sum(A[:d])+((N-d)//len(C))*sum(C) + sum(C[:res])
else:
    ans = sum(A) 
print(ans)
Buggy python submission (verdict: Runtime Error):
S,T=open(0).read().split()
def main():
    for i in range(1,len(T)+1):
        for j in range(i+1):
            print(T[j:(len(T)-i+j)], S[j:(len(S)-i+j)])
            if T[j:(len(T)-i+j)] in S[j:(len(S)-i+j)]:
                return i
                break
if T in S:
    print(0)
else:
    print(main())

Fixed submission:
S,T=open(0).read().split()
score = 0
for i in range(len(S)-len(T)+1):
    score=max(score,sum([T[k]==S[i+k] for k in range(len(T))]))
print(len(T)-score)
Buggy python submission (verdict: Runtime Error):
import itertools
import numpy as np

N = int(input(''))
L = (list(map(int, input('').split(' '))))
L = np.array(sorted(L))
set_L = set(L)
if len(set_L) <= 2:
    print(0)
else:
    K = {i:len(L[L==i]) for i in set_L}
    
i = 0
for team in itertools.combinations(K.keys(), 3):
    if (team[0] < team[1] + team[2]) & (team[1] < team[0] + team[2]) & (team[2] < team[0] + team[1]):
        i += K[team[0]]*K[team[1]]*K[team[2]]
print(i)

Fixed submission:
import itertools
import numpy as np

N = int(input(''))
L = (list(map(int, input('').split(' '))))
L = np.array(sorted(L))
set_L = set(L)

if len(set_L) <= 2:
    print(0)
else:
    K = {i:len(L[L==i]) for i in set_L}
    
    i = 0
    for team in itertools.combinations(K.keys(), 3):
        if (team[0] < team[1] + team[2]) & (team[1] < team[0] + team[2]) & (team[2] < team[0] + team[1]):
            i += K[team[0]]*K[team[1]]*K[team[2]]
    print(i)
Buggy python submission (verdict: Runtime Error):
import numpy as np
X, K, D = (list(map(int, input('').split(' '))))

sign = np.sign(X)*(-1)
if K%2 == 0:
    new_X = X
    for i in range(2*sign, (K+1)*sign, 2*sign):
        old_X = new_X
        new_X = i*D + X
        if np.abs(new_X) > np.abs(old_X):
            ans = np.abs(old_X)
            break
else:
    new_X = X
    for i in range(sign, (K+1)*sign, 2*sign):
        old_X = new_X
        new_X = i*D + X#2*sign*D
        if np.abs(new_X) > np.abs(old_X):
            ans = np.abs(old_X)
            break
            
try:
    print(ans)
except NameError:
    print(np.abs(new_X))

Fixed submission:
import numpy as np
X, K, D = (list(map(int, input('').split(' '))))
X = np.abs(X)

if np.abs(X)/D <= K:
    new_K = K - int(X/D)
    new_X = X - D*int(X/D)
    if new_K%2==0:
        print(new_X)
    else:
        print(np.abs(new_X-D))
else:
    print(np.abs(X-D*K))

Buggy python submission (verdict: Runtime Error):
import numpy as np

X, K, D = (list(map(int, input('').split(' '))))
dX = np.arange(-K,K+1,2)
new_X = X + D * dX
print(np.min(np.abs(new_X)))

Fixed submission:
import numpy as np
X, K, D = (list(map(int, input('').split(' '))))
X = np.abs(X)

if np.abs(X)/D <= K:
    new_K = K - int(X/D)
    new_X = X - D*int(X/D)
    if new_K%2==0:
        print(new_X)
    else:
        print(np.abs(new_X-D))
else:
    print(np.abs(X-D*K))

Buggy python submission (verdict: Runtime Error):
X, K, D = (list(map(int, input('').split(' '))))
dX = np.arange(-K,K+1,2)
new_X = X + D * dX
print(np.min(np.abs(new_X)))

Fixed submission:
import numpy as np
X, K, D = (list(map(int, input('').split(' '))))
X = np.abs(X)

if np.abs(X)/D <= K:
    new_K = K - int(X/D)
    new_X = X - D*int(X/D)
    if new_K%2==0:
        print(new_X)
    else:
        print(np.abs(new_X-D))
else:
    print(np.abs(X-D*K))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S = [''.join(sorted(input())) for i in range(N)]
ans=0
for elem in set(S):
    sum_ = S.count(elem)
    if sum_>=2:
        ans += sum_*(sum_-1)//2
print(ans)

Fixed submission:
import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S = [''.join(sorted(input())) for i in range(N)]
ans=0
for elem in set(S):
    sum_ = sum([s==elem for s in S])
    ans += sum_*(sum_-1)//2
print(ans)

Fixed submission:
import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))

Buggy python submission (verdict: Time Limit Exceeded):
N,*S=open(0).read().split()
S = [''.join(sorted(s)) for s in S]
ans=0
for elem in set(S):
    sum_ = sum([s==elem for s in S])
    ans += sum_*(sum_-1)//2
print(ans)

Fixed submission:
import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))

Buggy python submission (verdict: Time Limit Exceeded):
N,*S=open(0).read().split()
ans=0
def is_anagram(a,b):
    a = sorted(a)
    b = sorted(b)
    return True if a==b else False

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

Fixed submission:
import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N,*D=map(int,open(0).read().split())
for i in range(N):
  A=copy.deepcopy(D)
  del A[i]
  print(max(A))

Fixed submission:
N,*D=map(int,open(0).read().split())
S=sorted(D,reverse=True)
if S[1]==S[0]:
  [print(S[0]) for i in range(N)]
else:
  import numpy as np
  max_i=np.arange(N)[np.array(D)==S[0]]
  for i in range(N):
    if i==max_i:
      print(S[1])
    else:
      print(S[0])
Buggy python submission (verdict: Time Limit Exceeded):
import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s,g=A[-1],A[-1]
for i in range(2,N+1):
    g=math.gcd(g,A[-i])
    if math.gcd(s,A[-i])!=1:
        k=-1
    s*=A[-i]
if k==-1:
    if g==1:
        k=1
    else:
        k=2
print(ans[k])

Fixed submission:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return set(arr)

import math
N=int(input())
A=list(map(int,input().split()))
ans=['pairwise coprime','setwise coprime','not coprime']
k=0
s=factorization(A[0])
for a in A[1:]:
    tmp=factorization(a)-{1}
    if s&tmp==set():
        s|=tmp
    else:
        k=-1
        break
if k==-1:
    g=A[0]
    for a in A[1:]:
        g=math.gcd(g,a)
    if g==1:
        k=1
    else:
        k=2
print(ans[k])
Buggy python submission (verdict: Runtime Error):
print("Yes" if int(input())%9==o else "No")

Fixed submission:
S=input()
n=0
for s in S:
  n+=int(s)
print("Yes" if n%9==0 else "No")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h=deque([(ch-1,cw-1)])
c=0
while 1:
  done=[]
  while h:
    cx,cy=h.popleft()
    done.append((cx,cy))
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
print(visited[dh-1][dw-1])

Fixed submission:
from collections import deque

H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h=deque([(ch-1,cw-1)])
c=0
while 1:
  done=[]
  while h:
    cx,cy=h.popleft()
    done.append((cx,cy))
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
print(visited[dh-1][dw-1])