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

N,M = map(int,input().split())
mod=10**9+7
A=[]
for i in range(M):
  A +=[int(input())]

B=[1]
if 1 in A:
  B +=[0]
else:
  B +=[1]
for i in range(2,N+1):
  if i in A:
    B +=[0]
  else:
    B +=[(B[i-1]+B[i-2])%mod]
print(B[-1]%mod)

### FIXED CODE ###

N,M = map(int,input().split())
mod=10**9+7
A = {int(input()) for i in range(M)}

if 1 in A:
  x=0
else:
  x=1
B=[1,x]
for i in range(2,N+1):
  if i in A:
    B +=[0]
  else:
    B +=[(B[i-1]+B[i-2])%mod]
print(B[-1]%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
a=0
while k<=n+1:
    mi=0
    ma=0
    for t in range(k):
        mi+=t
        ma+=(n-t)
    a+=(ma-mi+1)
    k+=1
print(a)


### FIXED CODE ###

n,k=map(int,input().split())
d=0
for i in range(k,n+2):
    b=i*(i-1)/2
    c=i*(2*n-i+1)/2
    d+=(c-b+1)
print(int(d)%(10**9+7))
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
count = 0
for r in range((N//R)+2):
    for g in range((N//G)+2):
        for b in range((N//B)+2):
            if R*r + G*g + B*b == N:
                count +=1
print(count)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
count = 0
for a in range(0,N+1,R):
    if a%R == 0:
        for b in range(0,N-a+1,G):
            if b%G == 0:
                c = N-a-b
                if c%B == 0:
                    count +=1
print(count)
### BUGGY CODE ###

n,k  = map(int,input().split())
p = list(map(int, input().split()))
current_best = 0

for i in range(n-(k-1)):
  expect = (sum(p[i:i+k])+k)/2
  if expect > current_best:
    current_best = expect
print(current_best)

### FIXED CODE ###

n,k  = map(int,input().split())
p = list(map(int, input().split()))
current_best = 0
sum_list = [(1+p[0])/2]

if n == 1:
  print(sum_list[0])
  exit()

#累積和の計算
for i in range(n-1):
  sum_list.append(sum_list[-1]+(1+p[i+1])/2)
  
if n==k:
  print(sum_list[-1])
  exit()
  
for j in range(n-k):
  expect = sum_list[j+k]-sum_list[j]
  if expect > current_best:
    current_best = expect
print(current_best)
### BUGGY CODE ###

a=int(input())
ans=0
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd,numbers)
print(sum(gcd(i,j,k)for i in range(1,a+1) for j in range(1,a+1) for k in range(1,a+1)))

### FIXED CODE ###

a=int(input())
import math
print(sum(math.gcd(math.gcd(i,j),k)for i in range(1,a+1) for j in range(1,a+1) for k in range(1,a+1)))
### BUGGY CODE ###

n = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
m = sum(t)*2
g = [10**10]*(m+1)
l = [(0, 0, 0)]
for x, y in zip(t, v):
  l.append((l[-1][1], l[-1][1] + x*2, y))
for x, y, c in l:
  for i in range(m + 1):
    d = c
    if i < x:
      d += (x - i)*.5
    elif y < i:
      d += (i - y)*.5
    if g[i] > d:
      g[i] = d
print(sum(g)/2)

### FIXED CODE ###

n = int(input())
t = list(map(int, input().split())) + [0]
v = list(map(int, input().split())) + [0]
m = sum(t)*2
g = [10**10]*(m+1)
l = [(0, 0, 0)]
for x, y in zip(t, v):
  l.append((l[-1][1], l[-1][1] + x*2, y))
for x, y, c in l:
  for i in range(m + 1):
    d = c
    if i < x:
      d += (x - i)*.5
    elif y < i:
      d += (i - y)*.5
    if g[i] > d:
      g[i] = d
print(sum(g)/2)
### BUGGY CODE ###


import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))

ans = 0
for second in B:
    idx = bisect.bisect_left(A, second)
    first = len(A[:idx])

    idx = bisect.bisect_right(C, second)
    third = len(C[idx:])

    ans += (first*third)

print(ans)


### FIXED CODE ###


import bisect

N = int(input())
A = sorted(map(int, input().split()))
B = map(int, input().split())
C = sorted(map(int, input().split()))

ans = 0
for second in B:
    ai = bisect.bisect_left(A, second)
    ci = bisect.bisect_right(C, second)

    ans += (ai*(N-ci))

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

x, k, d = map(int, input().split())

for i in range(k):
    if abs(x - d) <= abs(x + d):
        x = abs(x - d)
    else:
        x = abs(x + d)
        
print(x)

### FIXED CODE ###

x, k, d = map(int, input().split())

if x < 0:
    if x + k * d < 0:
        print(-x - k * d)
    else:
        a = -x // d
        x += a * d
        if (k - a) % 2 == 0:
            print(-x)
        else:
            print(x + d)
            
else:
    if x - k * d > 0:
        print(x - k * d)
    else:
        a = x // d
        x -= a * d
        if (k - a) % 2 == 0:
            print(x)
        else:
            print(d - x)
### BUGGY CODE ###

A,B=map(int,input().split())
ans=A
i=1

while i<=B-A:
    ans=ans^(A+i)
    i+=1

print(ans)

### FIXED CODE ###

A,B=map(int,input().split())

def XOR(x):
    if x%4==1 or x%4==2:
        l="0"
    else:
        l="1"
    i=2
    while x>=(2**(i-1)):
        k=x%(2**i)
        if k<=2**(i-1)-1:
            l+="0"
        else:
            if k%2==0:
                l+="1"
            else:
                l+="0"
        i+=1    
    l=l[::-1]
    return(l)

b=XOR(B)
a=XOR(A-1).zfill(len(b))
ans=""

for j in range(len(b)):
    if b[j]==a[j]:
        ans+="0"
    else:
        ans+="1"

print(int(ans,2))
### BUGGY CODE ###

from functools import reduce


def main():

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

    def lcm_base(x, y):
        return (x * y) // gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

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

    a0 = a[0]
    p = 0
    while a0 % 2 == 0:
        a0 //= 2
        p += 1
    elm = 2**p
    for ai in a:
        if ai % elm != 0:
            print(0)
            return
        if ai % (2*elm) == 0:
            print(0)
            return

    lcm = lcm(*a)
    ans = (2*m+lcm) // (lcm*2)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(10**6)


def main():

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

    def lcm_base(x, y):
        return (x * y) // gcd(x, y)

    def lcm(*numbers):
        return reduce(lcm_base, numbers, 1)

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

    a0 = a[0]
    p = 0
    while a0 % 2 == 0:
        a0 //= 2
        p += 1
    elm = 2**p

    for ai in a:
        if (ai/elm) % 2 != 1:
            print(0)
            return

    lcm = lcm(*a)
    ans = (2*m+lcm) // (lcm*2)
    print(ans)


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

S=input()
K=int(input())
l = []
for alpha in [chr(i) for i in range(97, 97+26)]:
  indexs = [k for k, v in enumerate(list(S)) if v == alpha]
  for index in indexs:
    for j in range(index,len(S)+1):
      sub_s = S[index:j]
      l.append(sub_s)
  l = sorted(list(set(l)))
  if '' in l:
    l.remove('')
  if len(l) >= K:
    break
print(l[K-1])


### FIXED CODE ###

S=input()
K=int(input())
l = []
for alpha in [chr(i) for i in range(97, 97+26)]:
  indexs = [k for k, v in enumerate(list(S)) if v == alpha]
  for index in indexs:
    for j in range(index,min(index+6,len(S)+1)):
      sub_s = S[index:j]
      l.append(sub_s)
  l = sorted(list(set(l)))
  if '' in l:
    l.remove('')
  if len(l) >= K:
    break
print(l[K-1])
### BUGGY CODE ###

#154 d
def kitaichi(x):
    return (x+k)/2

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
for i in range(n-k+1):
    s=0
    s=sum(p[i:i+k])
    if s>=ans:
        ans=s
print(kitaichi(ans))


### FIXED CODE ###

#abc154 d
n,k=map(int,input().split())
p=list(map(int,input().split()))
wa=[0]*(n+1)

for i in range(n):
    wa[i+1]=p[i]+wa[i]

ans=0
for i in range(n-k+1):
    kitai=k+wa[i+k]-wa[i]
    if kitai>ans:
        ans=kitai
ans/=2
print(ans)
### BUGGY CODE ###

import numpy as np

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

a = [[0]*N for i in range(N)]
b = [0]*N

for i in range(N):
    a[i][(N+i-1)%N]=1
    a[i][i]=1

    b[i]=A[i]*2

x = np.linalg.solve(a, b) 

for i in range(N):
    print(int(x[(N+i-1)%N]),end=" ")



### FIXED CODE ###

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

a = [0]*N

sum_a=sum(A)
a[0]=sum_a
for i in range(1,N,2):
    a[0]-=2*A[i]
print(a[0],end=" ")

for i in range(1,N):
    a[i]=2*A[i-1]-a[i-1]
    print(a[i],end=" ")
### BUGGY CODE ###

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

if(1 in a == False):
  print(-1)
  exit()
if(a == list(map(lambda x: x+1, range(len(a))))):
  print(0)
  exit()

count = 0
for i in range(n):
  if(i < len(a)):
    while(len(a) > i and a[i] != i+1):
      a.pop(i)
      count += 1
 
if count == 0 or len(a) == 0:
  print(-1)
else:
  print(count)

### FIXED CODE ###

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

c = 0
for i in range(n):
  if a[i] == c + 1:
    c += 1
if c == 0:
  print(-1)
else:
  print(n - c)
### BUGGY CODE ###

import string

ALPHABETS = string.ascii_lowercase


def is_avairable(a):
    return bin(a).count('1') <= 1

s = input()
N = len(s)
a = [0] * (N + 1)
for i, c in enumerate(s):
    idx = ALPHABETS.index(c)
    a[i+1] = a[i] ^ (2 ** idx)

opt = [0] * (N + 1)
dp = [2 * (10 ** 5) + 1] * (2 ** 26)
dp[0] = 0
for i in range(1, N + 1):
    min = 2 * (10 ** 5) + 1
    for j in range(-1, 26):
        n = dp[a[i] ^ 2 ** j] if not j == -1 else dp[a[i] ^ 0]
        if n < min:
            min = n
    opt[i] = min + 1
    if dp[a[i]] > opt[i]:
        dp[a[i]] = opt[i]

print(opt[N])


### FIXED CODE ###

s = input()
N = len(s)
a = 0
dp = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]

for c in s:
    a = a ^ bits[ord(c)-ord('a')]
    dp[a] = min(dp.get(a, N), min([dp.get(a ^ bit, N) for bit in bits]) + 1)

print(dp[a] if dp[a] != 0 else 1)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    S = input().strip()
    n = len(S)
    T = ''

    ans = 0
    cnt = 0
    i = 0
    while i < n:
        if S[i:i+3] == 'ABC':
            cnt += 1 
            T += 'BCA'

            i += 3
        else:
            T += S[i]
            i += 1

    ans += cnt
    while cnt > 0:
        cnt = 0
        S = T
        T = ''
        i = 0
        while i < n:
            if S[i:i+3] == 'ABC':
                cnt += 1
                T += 'BCA'
                i += 3
            else:
                T += S[i]
                i += 1

        ans += cnt

    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    S = input().strip()
    n = len(S)

    T = ''
    i = 0
    while i < n:
        if S[i] == 'A':
            T += 'A'
            i += 1
        elif S[i:i+2] == 'BC':
            T += 'D'
            i += 2
        else:
            T += S[i]
            i += 1

    ans = 0
    cnt = 0
    for c in T:
        if c == 'A':
            cnt += 1
        elif c == 'D':
            ans += cnt
        else:
            cnt = 0

    return ans


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

n=int(input())
a=[]
c=[]
for _ in range(n):
    a.append(int(input()))
for i in range(n):
    c=a[i]
    del a[i]
    print(max(a))
    a.insert(i,c)
    

### FIXED CODE ###

n=int(input())
a=[]
c=[]
for _ in range(n):
    a.append(int(input()))
for i in a:
    c.append(i)

a.sort(reverse=True)

m_1=a[0]
m_2=a[1]
for i in range(n):
    if c[i]==m_1:
        print(m_2)
    else:
        print(m_1)
### BUGGY CODE ###

n, p = map(int, input().split())
s = list(input())

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        a = (int(s[i]) * 10 ** ((n - 1) - i)) % p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1

print(ans)


### FIXED CODE ###

n, p = map(int, input().split())

s = list(input())

ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        ans += cnt[d[i]]
        cnt[d[i]] += 1

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

import bisect
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
for j in range(m):
    b, c = map(int, input().split())
    i = bisect.bisect_left(A, c)
    start = min(i, b)
    A = A[:i] + [c for j in range(start)] + A[i:]
    A = A[start:]
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
D = []
for b, c in BC:
    D.extend([c for i in range(b)])
    if len(D) >= n:
        D = D[:n]
        break
for x in range(len(D)):
    if A[x] > D[x]:
        break
else:
    x += 1
print(sum(A[x:]) + sum(D[:x]))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

N = int(input())
A = list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
  tmpA = A[i]
  A[i] = A[i+1] if i != N-1 else A[i-1]
  ans = max(ans, reduce(gcd,A))
  A[i] = tmpA
print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

gcds = [-1] * N
gcds_rev = [-1] * N
for i in range(0,N):
  if i == 0: gcds[i] = A[0]
  else: gcds[i] = gcd(gcds[i-1], A[i])

  rev_i = N-1-i
  if rev_i == N-1: gcds_rev[rev_i] = A[-1]
  else: gcds_rev[rev_i] = gcd(gcds_rev[rev_i+1], A[rev_i])

ans = -float('inf')
for i in range(N):
  if i == 0:val = gcds_rev[1]
  elif i == N-1:val = gcds[-2]
  else: val = gcd(gcds[i-1], gcds_rev[i+1])
  ans = max(ans, val)
print(ans)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(1, n+1):
    A.append(int(input()))
for i in range(n):
    print(max(list(list(A[:i])+list(A[i+1:]))))

### FIXED CODE ###

n = int(input())
A = []
for i in range(1, n+1):
    A.append(int(input()))
A_srt = sorted(A)
A1, A2 = A_srt[-1], A_srt[-2]
for i in A:
    if i == A1:
        print(A2)
    else:
        print(A1)
### BUGGY CODE ###

import copy
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
ans=10**18
for i in range(1<<(H-1)):
    x=bin(i).count('1')
    cho=[0]*(x+1)
    f=1
    cnt=x
    for w in range(W):
        j=0
        nx=[0]*(x+1)
        for h in range(H):
          cho[j]+=int(S[h][w])
          nx[j]+=int(S[h][w])
          if cho[j]>K:
            if nx[j]>K:
              f=0
              break
            else:
              cho=copy.copy(nx)
              cnt+=1
          if (i>>h)&1:
            j+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

import copy
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
ans=10**18
for i in range(1<<(H-1)):
    x=bin(i).count('1')
    cho=[0]*(x+1)
    f=1
    cnt=x
    for w in range(W):
        j=0
        nx=[0]*(x+1)
        for h in range(H):
          cho[j]+=int(S[h][w])
          nx[j]+=int(S[h][w])
          if cho[j]>K:
            if nx[j]>K:
              f=0
              break
            else:
              cho=copy.copy(nx)
              cnt+=1
          if (i>>h)&1:
            j+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

import collections, sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for d in D:
    events += [[d, 2]]
events.sort()
block = set()
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(*ans, sep='\n')
### BUGGY CODE ###

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

w, v = [], []
for i in range(N):
    w_i, v_i = map(int, input().split())
    w.append(w_i)
    v.append(v_i)

# dp[i][j]: 荷物iまでにおける重さj以下の最大価値
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if w[i] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])

print(dp[-1][-1])

### FIXED CODE ###

import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

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

N, X = map(int, input().split())
lst = list(map(int, input().split()))
ans = []
for i in lst:
    ans.append(abs(i-X))
small = min(ans)
for i in ans:
    if i%small == 0:
        continue
    else:
        while i != small:
            i = i - small
            if i < small:
                small = small - i
print(small)

### FIXED CODE ###

N, X = map(int, input().split())
lst = list(map(int, input().split()))
ans = []
for i in lst:
    ans.append(abs(i-X))
small = min(ans)
for i in ans:
    if i%small != 0:
        while i%small != 0:
            i = i%small
            small = small - i
print(small)
### BUGGY CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        p = [0]*(c+1)
        for i in range(c+1):
            temp = 0
            for x in range(a, b+1):
                temp += pow(x, i, mod)
            p[i] = temp % mod
        for i in range(c+1):
            for j in range(i+1):
                temp = 0
                dp2[i] += dp[i-j]*p[j]
            dp2[i] = dp2[i] % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0

    p = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        q = [0]*(c+1)
        for i in range(c+1):
            q[i] = sum(p[i][a:b+1]) % mod
        for i in range(c+1):
            temp = 0
            for j in range(i+1):
                temp += dp[i-j]*q[j]
            dp2[i] = temp % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, ch-1, cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, y, x = heappop(Q)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    heappush(Q, (d, ny, nx))
            else:
                if dist[ny][nx]>d+1:
                    heappush(Q, (d+1, ny, nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.appendleft((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()
### BUGGY CODE ###

from copy import deepcopy


def main():
    h, w = map(int, input().split())
    a = [["#"] * (w + 2)]\
        + [["#"] + list(input()) + ["#"] for _ in range(h)]\
        + [["#"] * (w + 2)]

    fin = [["#"] * (w + 2) for _ in range(h + 2)]

    cnt = 0
    while a != fin:
        cnt += 1
        tmp = deepcopy(a)
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    tmp[i-1][j] = tmp[i+1][j] = tmp[i][j-1] = tmp[i][j+1] = "#"

        a = deepcopy(tmp)

    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from scipy.ndimage import distance_transform_cdt


def main():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]

    sq = [[1 if e == "." else 0 for e in row] for row in a]

    cnt = distance_transform_cdt(sq, metric="taxicab")

    print(cnt.max())


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

h, w, m = map(int, input().split())
cnt_h = [0] * h
cnt_w = [0] * w
bomb = [[False] * w for _ in range(h)]
for _ in range(m):
    y, x = map(int, input().split())
    cnt_h[y - 1] += 1
    cnt_w[x - 1] += 1
    bomb[y - 1][x - 1] = True
    
kouho_h = []
for i in range(h):
    if cnt_h[i] == max(cnt_h):
        kouho_h.append(i)
kouho_w = []
for i in range(w):
    if cnt_w[i] == max(cnt_w):
        kouho_w.append(i)

flag = False
for i in kouho_h:
    for j in kouho_w:
        if bomb[i][j] == False:
            flag = True
if flag:
    print(max(cnt_h) + max(cnt_w))
else:
    print(max(cnt_h) + max(cnt_w) - 1)

### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline
    h, w, m = map(int, input().split())
    cnt_h = [0] * h
    cnt_w = [0] * w
    bomb = defaultdict(lambda : 0)
    for _ in range(m):
        y, x = map(lambda x:int(x) - 1, input().split())
        cnt_h[y] += 1
        cnt_w[x] += 1
        bomb[(y, x)] = 1
        
    kouho_h = []
    kouho_w = []
    max_h = max(cnt_h)
    max_w = max(cnt_w)
    for i in range(h):
        if cnt_h[i] == max_h:
            kouho_h.append(i)
    for i in range(w):
        if cnt_w[i] == max_w:
            kouho_w.append(i)
    
    for i in kouho_h:
        for j in kouho_w:
            if bomb[(i, j)] == False:
                print(max_h + max_w)
                exit()
    print(max_h + max_w - 1)



if __name__ == '__main__':
    main()