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

H,W = map(int, input().split())
g = []
for _ in range(H):
    g.append(list(input()))

dp = [[10**9 for _ in range(W)] for __ in range(H)]

cnt = 0
#solve
def dfs(i, j, score, lc):
    
    if i < H and i >= 0 and j < W and j >= 0:
        if lc == '.' and g[i][j] == '#':
            score += 1
        dp[i][j] = min(dp[i][j], score)

        if i+1 < H:
            dfs(i+1, j, score, g[i][j])
        if j+1 < W:
            dfs(i, j+1, score, g[i][j])        

dfs(0, 0, 0, '.')
print(dp[H-1][W-1])

### FIXED CODE ###

H,W = map(int, input().split())
g = []
for _ in range(H):
    g.append(list(input()))

dp = [[10**9 for _ in range(W)] for __ in range(H)]

dp[0][0] = 1 if g[0][0] == '#' else 0
d = ([0,1], [1,0])
for ix in range(H):
    for jx in range(W):
        for dx,dy in d:
            ni = ix + dx
            nj = jx + dy
            if ni >= H or nj >= W:
                continue
            add = 0
            if g[ix][jx] == '.' and g[ni][nj] == '#':
                add += 1
            dp[ni][nj] = min(dp[ni][nj], dp[ix][jx] + add)


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

import math
n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    for k in range(1,n):
        a1[k]=a1[k-1]+a1[k]
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))


### FIXED CODE ###

import math
n , k = map(int, input().split())
a = list(map(int,input().split()))
a1=[0]*(n+1)
k = min(k,int(math.log2(n)*2.5))
for i in range(k):
    for j in range(n):
        st=j-a[j]
        gl=j+a[j]
        if st<0:
            st=0
        if gl>=n:
            gl=n-1
        a1[st]+=1
        a1[gl+1]-=1
    for k in range(1,n):
        a1[k]=a1[k-1]+a1[k]
    a=a1[:n]
    a1=[0]*(n+1)
print(' '.join([str(n) for n in a]))
### BUGGY CODE ###

import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if b == N:
        nlist.append(a)
    if a == 1:
        list1.append(b)
for i in list1:
    if i in nlist:
        print('POSSIBLE')
        flag = False
if flag:
    print('IMPOSSIBLE')

### FIXED CODE ###

import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

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

b = []
for i in range(n):
  b.append((a[i],i))
b.sort(reverse = True)

ans = 0
def f(l,r,i,h):
  global ans
  if i == n:
    ans = max(ans,h)
    return
  x = b[i][0]
  y = b[i][1]
  f(l+1,r,i+1,h+x*abs(y-l))
  f(l,r-1,i+1,h+x*abs(y-r))

f(0,n-1,0,0)
print(ans)

### FIXED CODE ###

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

b = []
for i in range(n):
  b.append((a[i],i))
b.sort(reverse = True)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
  x = b[i][0]
  y = b[i][1]
  for l in range(i+1):
    r = i-l
    dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l]+x*(y-l))
    dp[i+1][l] = max(dp[i+1][l],dp[i][l]+x*(n-1-r-y))

ans = 0
for i in range(n+1):
  ans = max(dp[n][i],ans)
print(ans)
#print(dp)
### BUGGY CODE ###

s=input()
ans=0
for  i in range(10**5):
  if s.count("BW")==0:
    print(ans)
    exit()
  s=s.replace("BW","WB",1)
  ans+=1
print(ans)

### FIXED CODE ###

s=input()
t=list(s).count("W")
A=[i for i,x in enumerate (list(s)) if x=="W"]
print(int(sum(A)-t*(t-1)/2))
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
G = csgraph_from_dense(A)
D = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    if D[i][j] < A[i][j]:
      print(-1)
      exit(0)
      
for i in range(N):
  for j in range(i+1,N):
    flg = True
    for k in range(N):
      if i == k or j == k:
        continue
      if D[i][j] == D[i][k] + D[k][j]:
        flg = False
    if flg:
      ans += D[i][j]
      
print(int(ans))

### FIXED CODE ###

#from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import copy
N = int(input())

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
D = copy.deepcopy(A)
for i in range(N):
  D[i][i] = 0
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      
#G = csgraph_from_dense(A)
#D = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    if D[i][j] < A[i][j]:
      print(-1)
      exit(0)
      
for i in range(N):
  for j in range(i+1,N):
    flg = True
    for k in range(N):
      if i == k or j == k:
        continue
      if D[i][j] == D[i][k] + D[k][j]:
        flg = False
    if flg:
      ans += D[i][j]
      
print(int(ans))
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
 
K = int(input())
 
import math
answer = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            gcd = math.gcd(math.gcd(i, j), k)
            answer += gcd
 
print(answer)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

K = int(input())

import math
answer = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            gcd = math.gcd(math.gcd(i, j), k)
            answer += gcd

print(answer)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(len(a)+1):
  print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(len(a)):
  b[a[i]-1]+=1
for j in range(len(b)):
  print(b[j])
### BUGGY CODE ###

import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = dijkstra(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


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

from itertools import combinations
N = int(input())
S = input()

res = set()
for pair in combinations(range(N), 3):
  res.add("".join([S[i] for i in pair]))

print(len(res))

### FIXED CODE ###

from itertools import product
N = int(input())
S = input()
res = 0
for pair in product(range(10), repeat=3):
  s = S[::]
  found = True
  for i,num in enumerate(pair):
    idx = s.find(str(num))
    if idx == -1:
      found = False
      break
    else:
      if idx+1 == N:
        if i != len(pair)-1:
          found = False
        break
      s = s[idx+1:]

  if found:
    res += 1

print(res)
### BUGGY CODE ###

import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


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

s = input()
n = len(s)
m = 2019

ans = 0

for i in range(n-1):
    for j in range(i+1,n+1):
        x = int(s[i:j])
        if x%m == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()
n = len(s)
m = 2019

a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
j = 1
for i in range(0,n):
    j = j * 10 % m
    ss = int(s[n-i-1])*j + z
    z = ss%m



    a += r[z]
    r[z] += 1

print(a)
### BUGGY CODE ###

n=int(input())
a=sorted(map(int,input().split()),reverse=True)
b=[]
while len(a):
    for i in range(n):
        a.remove(max(a))
        b.append(max(a))
        a.remove(max(a))
        a.remove(min(a))
print(sum(b))

### FIXED CODE ###

n=int(input())
a=sorted(map(int,input().split()))
print(sum(a[n::2]))
### BUGGY CODE ###

H=int(input())
count=0
m=1
while H:
  if H==1:
    count+=m
  else:
    m*=2
    H=int(H/2)
print(count)
    


### FIXED CODE ###

H=int(input())
n=0
while H!=1:
  H=int(H/2)
  n+=1
print(2**(n+1)-1)
### BUGGY CODE ###

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abcs = [list(map(int, input().split())) for i in range(M)]
INF = 10**9
dist_list = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

# distance[i][j]で(i, j)間の最短の移動距離を保持
for abc in abcs:
    a = abc[0]-1
    b = abc[1]-1
    c = abc[2]
    if c < dist_list[a][b]:
        dist_list[a][b] = c
        dist_list[b][a] = c
# ワーシャルフロイド
for i in range(1, N):
    for j in range(N):
        for k in range(N):
            dist_list[j][k] = min(dist_list[j][k], dist_list[j][i] + dist_list[i][k])
            dist_list[k][j] = dist_list[j][k]

# 総当たり
result = []


def permutation(data, res):
    global result
    if len(data) == 0:
        result.append(res)
        return

    for i in data:
        _res = res[::]
        _res.append(i)
        _data = data[::]
        _data.remove(i)
        permutation(_data, _res)


permutation(r, [])
min_distance = INF
for res in result:
    distance = 0
    for i in range(1, len(res)):
        x = res[i]-1
        y = res[i-1]-1
        distance += dist_list[x][y]
    if distance < min_distance:
        min_distance = distance
print(min_distance)

### FIXED CODE ###

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
abcs = [list(map(int, input().split())) for i in range(M)]
INF = 10**9
dist_list = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

# distance[i][j]で(i, j)間の最短の移動距離を保持
for abc in abcs:
    a = abc[0]-1
    b = abc[1]-1
    c = abc[2]
    if c < dist_list[a][b]:
        dist_list[a][b] = c
        dist_list[b][a] = c
# ワーシャルフロイド
for i in range(1, N):
    for j in range(N):
        for k in range(N):
            dist_list[j][k] = min(dist_list[j][k], dist_list[j][i] + dist_list[i][k])
            dist_list[k][j] = dist_list[j][k]

# 総当たり
result = []


def permutation(data, res):
    global result
    if len(data) == 0:
        result.append(res)
        return

    for i in data:
        _res = res[::]
        _res.append(i)
        _data = data[::]
        _data.remove(i)
        permutation(_data, _res)


permutation(r, [])
min_distance = INF
for res in result:
    distance = 0
    for i in range(1, len(res)):
        x = res[i]-1
        y = res[i-1]-1
        distance += dist_list[x][y]
    if distance < min_distance:
        min_distance = distance
print(min_distance)
### BUGGY CODE ###

K,S = map(int,input().split())

same_all = 0
same_two = 0
same_none = 0
K += 1

for i in range(1, K):
    if(i == S):
        same_two += 1
        
    for j in range(i,K):
        if (i + j == S):
            if (i == j):
                same_two += 1
            else:
                same_none += 1
            
        for k in range(j,K):
            if (i + j + k == S):
                if (i == j) and (j == k):
                    same_all += 1
                elif (i == j) or (j == k) or (i == k):
                    same_two += 1
                else:
                    same_none += 1                 

print(same_all + same_two*3 + same_none*6)

### FIXED CODE ###

K,S = map(int,input().split())

same_all = 0
same_two = 0
same_none = 0

for i in range(K, -1, -1):
    for j in range(S - i, -1, -1):
        if ( K<j or i<j):
            continue
        k = S-i-j
#         print(i,j,k)
        if (k <= K and k<=j):
            if(i == j and j == k):
                same_all += 1
            elif(i == j or i == k or k == j):
                same_two += 1
            else:
                same_none += 1


print(same_all + same_two*3 + same_none*6)
### BUGGY CODE ###

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


sum = 0
D = set(range(N))
E = set()
for i in D:
    E.add(i)
    tmp = 0
    for j in D - E:
        tmp += A[j]
    sum += A[i] * tmp

print(sum % (10**9+7))

### FIXED CODE ###

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


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

ans = 0
for i in range(N):
    ans += A[i] * (S[N-1] - S[i])

print(int(ans % (10**9 + 7)))
### BUGGY CODE ###

N = int(input())
P = list(map(int,(input().split())))
S = 0
max_1 = 0
max_2 = 0

for i in range(1,len(P)):
    max_1 = max(P[i-1],P[i])
    max_2 = min(P[i-1],P[i])
    S += max_2
    for j in range(i-1):
        n = i-j-2
        if P[n] > max_1:
            max_2 = max_1
            max_1 = P[n]
        elif P[n] > max_2:
            max_2 = P[n]
        S += max_2

print(S)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
 
left_bigger  = [0] + [i for i in range(N+1)]
right_bigger = [i+1 for i in range(N+1)] + [N+1]
 
E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v,i in E:
    l0=left_bigger[i]
    l1=left_bigger[l0]
    r0=right_bigger[i]
    r1=right_bigger[r0]
    ans += ((r1-r0)*(i-l0) + (r0-i)*(l0-l1))*v
    left_bigger[r0]=l0
    right_bigger[l0]=r0
print(ans)
### BUGGY CODE ###

def gauss_jordan(A):
  m=len(A)
  n=len(A[0])
  rank=0
  for col in range(n):
    pivot=-1
    for row in range(rank,m):
      if A[row][col]!=0:
        pivot=row
        break
    if pivot==-1:
      continue
    A[pivot],A[rank]=A[rank],A[pivot]
    for row in range(m):
      if row!=rank and A[row][col]!=0:
        for col2 in range(n):
          A[row][col2]^=A[rank][col2]      
    rank+=1
  if rank==len(A):
    return True
  else:
    return False

def make_vector(val):
  ret=[]
  for i in range(60,-1,-1):
    if val&(1<<i):
      ret.append(1)
    else:
      ret.append(0)
  return ret

t=int(input())
for _ in range(t):
  n=int(input())
  arr=list(map(int,input().split()))
  s=input()
  if s[-1]=='1':
    print(1)
    continue
  A=[make_vector(arr[-1])]
  for i in range(n-2,-1,-1):
    vector=make_vector(arr[i])
    if gauss_jordan(A+[vector]):
      if s[i]=='1':
        print(1)
        break
      if s[i]=='0':
        A.append(vector)
  else:
    print(0)

### FIXED CODE ###

def gauss_jordan(A):
  m=len(A)
  n=len(A[0])
  rank=0
  for col in range(n):
    pivot=-1
    for row in range(rank,m):
      if A[row][col]!=0:
        pivot=row
        break
    if pivot==-1:
      continue
    A[pivot],A[rank]=A[rank],A[pivot]
    for row in range(m):
      if row!=rank and A[row][col]!=0:
        for col2 in range(n):
          A[row][col2]^=A[rank][col2]      
    rank+=1
  if rank==len(A):
    return True
  else:
    return False

def make_vector(val):
  ret=[]
  for i in range(60,-1,-1):
    if val&(1<<i):
      ret.append(1)
    else:
      ret.append(0)
  return ret

t=int(input())
for _ in range(t):
  n=int(input())
  arr=list(map(int,input().split()))
  s=input()
  if s[-1]=='1':
    print(1)
    continue
  A=[make_vector(arr[-1])]
  for i in range(n-2,-1,-1):
    vector=make_vector(arr[i])
    if gauss_jordan(A+[vector]):
      if s[i]=='1':
        print(1)
        break
      if s[i]=='0':
        A.append(vector)
  else:
    print(0)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for sum_w in range(W+1):
        if sum_w >= wv[i][0]:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][sum_w] = dp[i][sum_w]

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

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())

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

for i in range(N):
    w, v = map(int, input().split())
    np.maximum(dp[:W-w+1]+v, dp[w:], out=dp[w:])
print(dp[-1])
### BUGGY CODE ###

import numpy as np
n,m = map(int,input().split())

p = np.zeros(n+1,dtype=int)
s = np.zeros(n+1,dtype=int)

s[1]=1

a = np.zeros(m,dtype=int)
b = np.zeros(m,dtype=int)


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

for i in range(1,n+1):
    t=False
    for j in range(1,n+1):
        if s[j] == i:
            for k in range(m):
                if a[k]==j and p[b[k]] == 0:
                    p[b[k]]=a[k]
                    s[b[k]]=i+1
                    t=True

                if b[k]==j and p[a[k]]==0:
                    p[a[k]]=b[k]
                    s[a[k]]=i+1
                    t=True
    if t==False:
        break
    
if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)


### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())

p = [0 for i in range(n+1)]
q = list()
q2 = list()

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)


q2.append(1)

while 1:
    q=q2
    q2=[]

    while len(q):
        v = q.pop()
        
        for nv in g[v]:
            if p[nv] == 0:
                p[nv]=v
                g[nv].remove(v)
                q2.append(nv)
    if len(q2)==0:
        break

if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)
### BUGGY CODE ###

from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
numset = set(a)
maxval = 10**6
dp = [0]*(maxval+1)
for i in range(n):
    if dp[a[i]] == 0 and (i == n-1 or a[i] != a[i+1]):
        ans += 1
    j = a[i]
    while j <= maxval:
        dp[j] += 1
        j += a[i]
print(ans)

### FIXED CODE ###

from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
maxval = a[-1]
seen = set()
for i in range(n):
    if a[i] not in seen and (i == n-1 or a[i] != a[i+1]):
        ans += 1
    j = a[i]
    while j <= maxval:
        seen.add(j)
        j += a[i]
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int,input().split()))

ans_str = str(a.index(1)+1)

for i in range(1,N):
    ans_str += " "+ str(a.index(i+1)+1)
print(ans_str)

### FIXED CODE ###

# -*- coding:utf-8 -*-
N = int(input())
a = list(map(int,input().split()))

L = {}

for i in range(N):
    L[i] = a[i]

sort_L = sorted(L.items(), key=lambda x:x[1])

for j in sort_L:
    print(j[0]+1, end =" ")
### BUGGY CODE ###

n,m=map(int,input().split())
a=m//n
if m//n<=int(m**0.5):
    for i in range(m//n,0,-1):
        if m%i==0:
            print(i)
            break
else:
    for i in range(m//n,0,-1):
        if m%i==0:
            print(i)
            break

### FIXED CODE ###

n, m = list(map(int,input().split()))
def solve():
    for i in range(m//n, 0, -1):
        if m % i == 0:
            if m//i>= n:
                print(i)
                break
solve()
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

C0 -= 1
C1 -= 1
D0 -= 1
D1 -= 1

map = []
for _ in range(H):
    map.append(input())

inf = 1000000000

q = deque([[C0, C1]])
dist = [[inf for a in range(1100)]for b in range(1100)]
dist[C0][C1] = 0

walk0 = [1, 0, -1, 0]
walk1 = [0, 1, 0, -1]


while q:
    now = q.popleft()
    d = dist[now[0]][now[1]]

    for v in range(4):
        wnxt0 = now[0] + walk0[v]
        wnxt1 = now[1] + walk1[v]

        if wnxt0 < 0 or wnxt0 > H - 1: continue
        elif wnxt1 < 0 or wnxt1 > W - 1: continue
        elif map[wnxt0][wnxt1] == "#": continue
        elif dist[wnxt0][wnxt1] <= d: continue
        
        dist[wnxt0][wnxt1] = d
        q.appendleft([wnxt0, wnxt1])

    for x in [-2, -1, 0, 1, 2]:
        for y in [-2, -1, 0, 1, 2]:
            mnxt0 = now[0] + y
            mnxt1 = now[1] + x

            if mnxt0 < 0 or mnxt0 > H - 1: continue
            elif mnxt1 < 0 or mnxt1 > W - 1: continue
            elif map[mnxt0][mnxt1] == "#": continue
            elif dist[mnxt0][mnxt1] <= d + 1: continue

            dist[mnxt0][mnxt1] = d + 1
            q.append([mnxt0, mnxt1])

ans = dist[D0][D1]

if ans == inf:
    ans = -1

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

C0 -= 1
C1 -= 1
D0 -= 1
D1 -= 1

map = []
for _ in range(H):
    map.append(input())

inf = 1000000000

q = deque([[C0, C1]])
dist = [[inf for a in range(1100)]for b in range(1100)]
dist[C0][C1] = 0

walk0 = [1, 0, -1, 0]
walk1 = [0, 1, 0, -1]


while q:
    now = q.popleft()
    d = dist[now[0]][now[1]]

    for v in range(4):
        wnxt0 = now[0] + walk0[v]
        wnxt1 = now[1] + walk1[v]

        if wnxt0 < 0 or wnxt0 > H - 1: continue
        elif wnxt1 < 0 or wnxt1 > W - 1: continue
        elif map[wnxt0][wnxt1] == "#": continue
        elif dist[wnxt0][wnxt1] <= d: continue
        
        dist[wnxt0][wnxt1] = d
        q.appendleft([wnxt0, wnxt1])

    for x in [-2, -1, 0, 1, 2]:
        for y in [-2, -1, 0, 1, 2]:
            mnxt0 = now[0] + y
            mnxt1 = now[1] + x

            if mnxt0 < 0 or mnxt0 > H - 1: continue
            elif mnxt1 < 0 or mnxt1 > W - 1: continue
            elif map[mnxt0][mnxt1] == "#": continue
            elif dist[mnxt0][mnxt1] <= d + 1: continue

            dist[mnxt0][mnxt1] = d + 1
            q.append([mnxt0, mnxt1])

ans = dist[D0][D1]

if ans == inf:
    ans = -1

print(ans)