Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p04019 (python)

Fixed submission:
s = input()
kita, minami = sorted([s.count('N'),s.count('S')])
nisi, higasi = sorted([s.count('W'),s.count('E')])
result = ['No','Yes']
r = 1
if kita==minami or kita*minami > 0:
    r *= 1
else:
    r = 0

if nisi==higasi or nisi*higasi > 0:
    r *= 1
else:
    r = 0
print(result[r])

Buggy submission (verdict: Runtime Error):
s = input()
kita, minami = sorted([s.count('N'),s.count('S')])
nisi, higasi = sorted([s.count('W'),s.count('E')])
result = ['No','Yes']
r = 1
if kita==minami:
    continue
elif kita*minami > 0:
    continue
else:
    r *= 0
if nisi==higasi:
    continue
elif nisi*higasi > 0:
    continue
else:
    r = 0
print(result[r])
Problem p02584 (python)

Fixed submission:
X, K, D = map(int, input().split())


def f(C):
    NX = float("inf")
    if C > K:
        return NX

    if K % 2 == 0:
        if C % 2 == 0:
            NX = abs(abs(X) - C * D)
        else:
            NX = abs(abs(X) - (C + 1) * D)
            if C > 0:
                NX = min(NX, abs(abs(X) - (C - 1) * D))
    else:
        if C % 2 == 0:
            NX = abs(abs(X) - (C + 1) * D)
            if C > 0:
                NX = min(NX, abs(abs(X) - (C - 1) * D))
        else:
            NX = abs(abs(X) - C * D)

    return NX


C = min(abs(X) // D, K)

print(min(f(C), f(C + 1)))

Buggy submission (verdict: Runtime Error):
X, K, D = map(int, input().split())


def f(C):
    NX = float("inf")
    if C > K:
        return NX

    if K % 2 == 0:
        if C % 2 == 0:
            NX = abs(abs(X) - C * D)
        else:
            NX = abs(abs(X) - (C + 1) * D)
            if C > 0:
                NX = min(NX, abs(abs(X) - (C - 1) * D))
    else:
        if C % 2 == 0:
            NX = abs(NX, abs(X) - (C + 1) * D)
            if C > 0:
                NX = min(NX, abs(abs(X) - (C - 1) * D))
        else:
            NX = abs(abs(X) - C * D)

    return NX


C = min(abs(X) // D, K)

print(min(f(C), f(C + 1)))
Problem p02844 (python)

Fixed submission:
N = int(input())
S = input()

right = [[0 for _ in range(10)] for _ in range(N + 1)]
left = [[0 for _ in range(10)] for _ in range(N + 1)]
C = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]

for i in range(N - 1):
    for j in range(10):
        right[i + 1][j] += right[i][j]
    right[i + 1][int(S[i])] += 1

for i in range(N - 1, 0, -1):
    for j in range(10):
        left[i][j] += left[i + 1][j]
    left[i][int(S[i])] += 1

for i in range(1, N - 1):
    for a in range(10):
        for b in range(10):
            if right[i][a] != 0 and left[i + 1][b] != 0:
                C[a][int(S[i])][b] += 1

res = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if C[i][j][k] != 0:
                res += 1

print(res)

Buggy submission (verdict: Runtime Error):
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  string S;
  cin >> N >> S;
  vector<int> left(10, 0), right(10, 0);
  left[S[0] - '0']++;
  for (int i = 2; i < N; i++) {
    right[S[i] - '0']++;
  }
  vector<int> cnts(1000, 0);
  for (int i = 1; i < N - 1; i++) {
    int b = S[i] - '0';
    for (int a = 0; a < 10; a++) {
      for (int c = 0; c < 10; c++) {
        if (left[a] == 0 || right[c] == 0) continue;
        cnts[100 * a + 10 * b + c]++;
      }
    }
    left[S[i] - '0']++;
    right[S[i + 1] - '0']--;
  }
  int res = 0;
  for (int i = 0; i < 1000; i++) {
    if (cnts[i] != 0) res++;
  }
  cout << res << '\n';
  return 0;
}
Problem p03138 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))

binlen = 0
while 2 ** binlen <= K:
    binlen += 1
binlen -= 1

if binlen < 0:
    print(sum(A))
    exit()

bitcount = [0] * (len(bin(max(A))) - 2)
for a in A:
    for i, s in enumerate(bin(a)[::-1][:-2]):
        if s == "1":
            bitcount[i] += 1

maxn = 2 ** binlen
mid = N / 2

for i in range(binlen + 1):
    if i < len(bitcount):
        if bitcount[i] < mid and i != binlen:
            maxn += 2 ** i
        elif bitcount[i] > mid and i == binlen:
            maxn -= 2 ** i
    elif i != binlen:
        maxn += 2 ** i

pos = 0
while maxn > K:
    if bin(maxn)[2:][pos] == "1" and bin(K)[2:][pos] == "0":
        maxn -= 2 ** (len(bin(maxn)) - 3 - pos)
    pos += 1

print(sum([maxn ^ a for a in A]))

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))

binlen = len(bin(max(A))) - 2
while 2 ** binlen > K:
    binlen -= 1

if binlen < 0:
    print(sum(A))
    exit()

bitcount = [0] * (len(bin(max(A))) - 2)
for a in A:
    for i, s in enumerate(bin(a)[::-1][:-2]):
        if s == "1":
            bitcount[i] += 1

maxn = 2 ** binlen
mid = N / 2

for i in range(binlen + 1):
    if bitcount[i] < mid and i != binlen:
        maxn += 2 ** i
    elif bitcount[i] > mid and i == binlen:
        maxn -= 2 ** i
    elif i >= len(bitcount):
        maxn += 2 ** i

print(sum([maxn ^ a for a in A]))
Problem p03149 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N = sorted(list(map(int, input().split())))
if N[0] == 1 and N[1] == 4 and N[2] == 7 and N[3] == 9:
    print("YES")
else:
    print("NO")

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = list(map(int, input().split())).sorted()
if N[0] == 1 and N[1] == 4 and N[2] == 7 and N[3] == 9:
    print("YES")
else:
    print("NO")
Problem p03215 (python)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))


def countMask(a):
    ret = 0
    for x in cand:
        if (x & a) == a:
            ret += 1
    return ret


cand = []
for i in range(N):
    sum = 0
    for j in range(i, N):
        sum += A[j]
        cand.append(sum)

ans = 0

for i in range(40, -1, -1):
    if (countMask(ans | (1 << i)) >= K):
        ans |= 1 << i

print(ans)

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))


def countMask(a):
    ret = 0
    for x in cand:
        if (x & a) == a:
            ret += 1
    return ret


cand = []
for i in range(N):
    sum = 0
    for j in range(j, N):
        sum += A[j]
        cand.append(sum)

ans = 0

for i in range(40, -1, -1):
    if (countMask(ans | (1 << i)) >= K):
        ans |= 1 << i

print(ans)
Problem p03227 (python)

Fixed submission:
S = input()

if len(S) == 2:
    print(S)
else:
    print(S[::-1])

Buggy submission (verdict: Runtime Error):
N = int(input())
A = sorted([int(input()) for i in range(N)])

if N % 2 == 0:
    print(2 * (sum(A[N // 2:]) - sum(A[:N // 2])) - (A[N // 2] - A[N // -1]))
else:
    print(2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2])) - min(A[N // 2] - A[N // 2 - 1], A[N // 2 + 1] - A[N // 2]))

Buggy submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

for i in range(K):
    if A % 2 == 1:
        A -= 1
    A /= 2
    A, B = B + A, A

if K % 2 == 1:
    A, B = B, A
print(int(A), int(B))

Buggy submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

for i in range(K):
    if A % 2 == 1:
        A -= 1
    A /= 2
    A, B = B + A, A

if K % 2 == 1:
    A, B = B, A
print(int(A), int(B))
Problem p03228 (python)

Fixed submission:
A, B, K = map(int, input().split())

for i in range(K):
    if A % 2 == 1:
        A -= 1
    A /= 2
    A, B = B + A, A

if K % 2 == 1:
    A, B = B, A
print(int(A), int(B))

Buggy submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

for i in range(K):
	if A == 0 or B == 0:
		break
    if A % 2 == 1:
        A -= 1
    A /= 2
    A, B = B + A, A

print(int(A), int(B))

Buggy submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

for i in range(K):
	if A == 0 or B == 0:
		break
    if A % 2 == 1:
        A -= 1
    A /= 2
    A, B = B + A, A

print(int(A), int(B))
Problem p03229 (python)

Fixed submission:
N = int(input())
A = sorted([int(input()) for i in range(N)])

if N % 2 == 0:
    print(2 * (sum(A[N // 2:]) - sum(A[:N // 2])) - (A[N // 2] - A[N // 2 - 1]))
else:
    print(2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2])) - min(A[N // 2] - A[N // 2 - 1], A[N // 2 + 1] - A[N // 2]))

Buggy submission (verdict: Runtime Error):
N = input()
A = sorted([input() for i in range(N)])

if N % 2 == 0:
    ans = 2 * (sum(A[N // 2:]) - sum(A[:N // 2])) - (A[N // 2] - A[N // -1])
else:
    ans = 2 * (sum(A[N // +1:]) - sum(A[:N // 2])) - min(A[N // 2] - A[N // 2 - 1], A[N // 2 + 1] - A[N // 2])

print(ans)
Problem p03231 (python)

Fixed submission:
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()

    g = gcd(N, M)
    for i in range(g):
        if S[i * N // g] != T[i * M // g]:
            print("-1")
            exit()
    print(N * M // g)

main()

Buggy submission (verdict: Runtime Error):
from math import gcd

N, M = map(int, input().split())
S = input(); T = input()

nm_gcd = gcd(N, M)
n, m = M // nm_gcd, N // nm_gcd
ans = N * M // nm_gcd
for i in range(nm_gcd):
    if S[i * m] != T[i * n]:
        ans = -1
        break

print(ans)

Buggy submission (verdict: Runtime Error):
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def main():
    N, M = map(int, input().split())
    S, T = input().split()

    g = gcd(N, M)
    for i in range(g):
        if S[i * N / g] == T[i * M / g]:
            print("-1")
            exit()
    print(N * M / g)

main()
Problem p03289 (python)

Fixed submission:
S = input()

count = 0
ans = True

if S[0] != "A":
    ans = False
if not "C" in S[2:-1]:
    ans = False
for s in S:
    if s.isupper():
        count += 1
if count > 2:
    ans = False

print("AC" if ans else "WA")

Buggy submission (verdict: Runtime Error):
S = input()

count = 0
tf = True
if S[0] != "A" or S[1] == "C" or S[-1] == "C":
    tf = False

for i in range(len(S)):
	if tf:
		break
    if i == 0:
        continue
    if S[i] == "C":
        count += 1
    elif not S[i].islower():
        tf = False

if tf and count == 1:
    print("AC")
else:
    print("WA")
Problem p03290 (python)

Fixed submission:
D, G = map(int, input().split())
PC = [tuple(map(int, input().split())) for _ in range(D)]

res = float("inf")
for bit in range(1 << D):
    summ = 0
    num = 0
    for i in range(D):
        if ((bit >> i) & 1):
            summ += (i + 1) * 100 * PC[i][0] + PC[i][1]
            num += PC[i][0]
    if summ >= G:
        res = min(res, num)
    for i in range(D - 1, -1, -1):
        if ((bit >> i) & 1):
            continue
        for _ in range(PC[i][0] - 1):
            summ += (i + 1) * 100
            num += 1
            if summ >= G:
                res = min(res, num)
                break
print(res)

Buggy submission (verdict: Runtime Error):
D, G = map(int, input().split())
PC = [tuple(map(int, input().split()))]

res = float("inf")
for bit in range(1 << D):
    sum = 0
    num = 0
    for i in range(D):
        if ((bit >> i) & 1):
            sum += (i + 1) * 100 * P[i] + C[i]
            num += P[i]
    if sum >= G:
        res = min(res, num)
    for i in range(D - 1, -1, -1):
        if ((bit >> i) & 1):
            continue
        for j in range(P[i] - 1):
            sum += (i + 1) * 100
            num + +
        if sum >= G:
            res = min(res, num)
            break
    print(res)
Problem p03318 (python)

Fixed submission:
K = int(input())


def dsum(n):
    return sum(list(map(int, str(n))))


def g(n):
    return n / dsum(n)

j = 1
order = 1
for i in range(K):
    print(j)
    if g(j + 10 ** (order - 1)) > g(j + 10 ** order):
        order += 1
    j += 10 ** (order - 1)

Buggy submission (verdict: Runtime Error):
def dsum(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret


def g(n):
    return n / dsum(n)

K = int(input())

res = []
base = 1
for i in range(15):
    for j in range(1, 150):
        res.append(base * (j + 1) - 1)
    base *= 10

res.sort()
res = list(set(res))

ans = []
print(res[:20])
for i, r in enumerate(res):
    flag = true
    for j in range(i + 1, len(res)):
        if g(r) > g(res[j]):
            flag = False
            break
    if flag:
        ans.append(r)

for k in range(K):
    print(ans[k])
Problem p03330 (python)

Fixed submission:
import itertools


def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    CC = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]

    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)

    print(res)

main()

Buggy submission (verdict: Runtime Error):
import itertools
import sys
input = sys.stdin.readline()


def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    CC = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]

    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)

    print(res)

main()

Buggy submission (verdict: Runtime Error):
import itertools
import sys
input = sys.input.readline()


def main():
    N, C = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(C)]
    CC = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    cost = [[0 for _ in range(C)] for _ in range(3)]
    for c in range(C):
        for i in range(N):
            for j in range(N):
                cost[(i + j) % 3][c] += D[CC[i][j]][c]

    res = float("inf")
    color = [i for i in range(C)]
    for i, c in enumerate(list(itertools.permutations(color, 3))):
        tmp = 0
        for it in range(3):
            tmp += cost[it][c[it]]
        res = min(res, tmp)

    print(res)

main()
Problem p03380 (python)

Fixed submission:
N = int(input())
A = sorted(list(map(int, input().split())))
y = A.pop(-1)
print(y, min(A, key=lambda x: abs(y - 2 * x)))

Buggy submission (verdict: Runtime Error):
from math import factorial
N = int(input())
A = sorted(list(map(int, input().split())))
ret = []

pos = 1
maxn = 0
for i, a in enumerate(A):
    if a == 0:
        maxn = 1
        ans = (a, A[pos])
        continue
    minn = [abs(A[pos] / a - 2), (a, A[pos])]
    while pos < N:
        if minn[0] < abs(A[pos] / a - 2):
            break
        minn[0] = abs(A[pos] / a - 2)
        pos += 1
    if maxn < factorial(minn[1][1]) / factorial(minn[1][0]):
        maxn = factorial(minn[1][1]) / factorial(minn[1][0])
        ans = minn[1]
    if i == pos:
        pos += 1
    if pos >= N:
        break
print(ans[1], ans[0])
Problem p03401 (python)

Fixed submission:
N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = []
for i in range(N + 1):
    cost.append(abs(A[i + 1] - A[i]))
scost = sum(cost)
for i in range(N):
    print(scost - cost[i] - cost[i + 1] + abs(A[i + 2] - A[i]))

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = []
for i in range(N + 1):
    cost.append(abs(A[i + 1] - A[i]))
scost = sum(cost)
for i in range(N):
    print(S - cost[i] - cost[i + 1] + abs(A[i + 2] - A[i]))
Problem p04012 (python)

Fixed submission:
import collections

w = input()
c = collections.Counter(w)
if all(i % 2 == 0 for i in c.values()):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  string w;
  cin >> w;

  map<char, int> count;
  for (auto s : w) {
    count[s] += 1;
  }
  for (auto itr = count.begin(); itr != count.end(); itr++) {
    if (itr->second % 2 == 1) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}
Problem p04013 (python)

Fixed submission:
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

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

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

print(dp[N][N * maxn] - 1)

Buggy submission (verdict: Runtime Error):
N, A = map(int, input().split())
# X = list(map(lambda x: int(x) - A, input().split()))
X = list(map(int, input().split()))

dp = [[[0 for _ in range(max(X) * N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(max(X) * N + 1):
            dp[i + 1][j][k] += dp[i][j][k]
            if k >= X[i]:
                dp[i + 1][j + 1][k] += dp[i][j][k - X[i]]

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

print(ans)
Problem p04046 (python)

Fixed submission:
import math
MOD = 10 ** 9 + 7
H, W, A, B = map(int, input().split())
maxf = H + W

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = i * f[i - 1] % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = invf[i] * i % MOD

comb = lambda a, b: f[a + b] * invf[a] * invf[b] % MOD

ans = 0
for x in range(B, W):
    ans += comb(x, H - A - 1) * comb(W - 1 - x, A - 1) % MOD
print(ans % MOD)

Buggy submission (verdict: Runtime Error):
import math
const MOD = 1000000007


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


def main():
    H, W, A, B = map(int, input().split())
    nr = 0
    for i in range(1, N - A + 1):
        nr = nr + comb(i - 1, B + i - 2) * comb(m - b - 1, m + n - b - i - 1) % MOD
    print(nr % MOD)

main()
Problem p02558 (python)

Fixed submission:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x, y = find(x), find(y)
    if x == y: return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True

N, Q = map(int, input().split())
par = [-1]*N
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        unite(u, v)
    else:
        if find(u)==find(v):
            print(1)
        else:
            print(0)

Buggy submission (verdict: Runtime Error):
class UnionFind:
    def __init__(self, size):
        self.par = [-1] * size
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.par[self.find(x)]

N, Q = map(int, input().split())
uf = Unionfind(N)
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uf.unite(u, v)
    else:
        if uf.same(u, v):
            print(1)
        else:
            print(0)
Problem p02574 (python)

Fixed submission:
import sys
n = int(input())
a = list(map(int, input().split()))

def prime_decomposition(n):
    i = 2
    table = []
    while i**2 <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1: table.append(n)
    return set(table)

pri_0 = prime_decomposition(a[0])
pri_1 = prime_decomposition(a[1])
ans = pri_0&pri_1

if len(ans):
    for i in range(2, n):
        res = prime_decomposition(a[i])
        ans &= res
        if not ans:
            print('setwise coprime')
            sys.exit()
    print('not coprime')

else:
    ans = pri_0 | pri_1
    for i in range(2, n):
        res = prime_decomposition(a[i])
        for i in res:
            if i in ans:
                print('setwise coprime')
                sys.exit()
        ans |= res
    print('pairwise coprime')

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int, input().split()))

def prime_decomposition(n):
    i = 2
    table = []
    while i**2 <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1: table.append(n)
    return set(table)

pri_0 = prime_decomposition(a[0])
pri_1 = prime_decomposition(a[1])

if len(pri_0&pri_1):
    for i in range(2, n):
        res = prime_decomposition(a[i])
        ans &= res
        if not ans:
            print('setwise coprime')
            sys.exit()
    print('not coprime')

else:
    ans = pri_0 | pri_1
    for i in range(2, n):
        res = prime_decomposition(a[i])
        for i in res:
            if i in ans:
                print('setwise coprime')
                sys.exit()
        ans |= res
    print('pairwise coprime')
Problem p02579 (python)

Fixed submission:
from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [input() for _ in range(H)]

d = [[-1]*W for _ in range(H)]

que = deque([[cw, ch, 0]])
while que:
    x, y, cost = que.popleft()
    if d[y][x]==-1 or d[y][x]>cost:
        d[y][x] = cost
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and s[ny][nx]!='#':
                    if abs(dx)+abs(dy) == 1:
                        que.appendleft([nx, ny, cost])
                    else:
                        que.append([nx, ny, cost+1])  
print(d[dh][dw])

Buggy submission (verdict: Runtime Error):
def main():
    from sys import stdin
    from collections import deque
    import sys
    H, W = map(int, stdin.readline().split())
    ch, cw = map(int, stdin.readline().split())
    dh, dw = map(int, stdin.readline().split())
    ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
    S = [input() for _ in range(H)]
    d = [[0]*W for _ in range(H)]

    que = deque([[cw, ch]])
    count = 0
    while que:
        while que:
            x, y = que.popleft()
            if x == dw and y == dh:
                print(count)
                sys.exit()
                
            d[y][x] = -1
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nnx, nny = x+i, y+j
                    if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                        d[nny][nnx] = 1
        
            for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                    if nx == dw and ny == dh:
                        print(count)
                        sys.exit()
                
                    d[ny][nx] = -1
                    for i in range(-2, 3):
                        for j in range(-2, 3):
                            nnx, nny = nx+i, ny+j
                            if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                                d[nny][nnx] = 1
                    que.append([nx, ny])
                
        for i in range(W):
            for j in range(H):
                if d[j][i] == 1:
                    d[j][i] == -1
                    que.append([i, j])
        count += 1
    print(-1)
if __name__ == __main__:
	main()