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

e,a = map(int,input().split())
cnt =0
while True:
    if e==0 and a==0:
        break
    else:
        for i in range(1,a):
            for j in range(i+1,a):
                for k in range(j+1,a):
                    if i+j+k ==a:
                        cnt +=1
print(cnt)


### FIXED CODE ###

while True:
    e,a = map(int,input().split())
    if e ==0 and a ==0:
        break
    cnt = 0
    for i in range(1,e+1):
        for j in range(1,e+1):
            if j<=i:
                continue
            X = a - (i + j)
            if X > j and X <=e:
                cnt +=1
    print(cnt)
### BUGGY CODE ###

def half_enumeration(a, *, func):
    """正しい英訳は不明"""
    n = len(a)
    h = n // 2

    def enum(h, *, second_half: bool = False):
        p = set()
        if second_half:
            b = a[h:]
        else:
            b = a[:h]

        for x in b:
            q = set()
            for e in p:
                q.add(func(e, x))
            p.add(x)
            p.update(q)
        return p

    return enum(h), enum(h, second_half=True)


def main():
    from itertools import chain
    from operator import add

    INF = 40 * 100 + 1

    N, Ma, Mb = map(int, input().split())

    def update(e, x):
        return e[0] + x[0], e[1] + x[1]

    xcs = []
    for _ in range(N):
        ai, bi, ci = map(int, input().split())
        x = Ma * bi - Mb * ai  # Σai:Σbi=Ma:Mb<->Ma*Σbi-Mb*Σai=0
        xcs.append((x, ci))

    p1, p2 = half_enumeration(xcs, func=update)

    ans = INF
    for x, c in chain(p1, p2):
        if x == 0 and ans > c:
            ans = c
    for x1, c1 in p1:
        for x2, c2 in p2:
            if x1 + x2 == 0 and ans > c1 + c2:
                ans = c1 + c2
    print(-1 if ans == INF else ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[[inf for _ in range(N_max * b_max + 1)] for _ in range(N_max * a_max + 1)] for _ in range(N_max + 1)]
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            if a + aa < N_max * a_max + 1 and b + bb < N_max * b_max + 1:
                dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, W = map(int, input().split())
    dp = [0] * (W + 1)
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(w, W+1):
            j = dp[i]
            if dp[i-w] < j + v:
                dp[i-w] = j + v

    print(max(dp))


main()


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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 ###

def main():
  n=int(input())
  a=list(map(int,input().split()))
  ans=[0]*n
  ans[0]=sum([a[i]*(-1)**i for i in range(n)])
  for i in range(1,n):
    ans[i]=sum((a[j]*(-1)**(i+j+1) if j<i else a[j]*(-1)**(i+j) for j in range(n)))
  print(*ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  a=list(map(int,input().split()))
  ans=[0]*n
  ans[0]=sum([a[i]*(-1)**i for i in range(n)])
  for i in range(1,n):
    ans[i]=ans[i-1]*(-1)+2*a[i-1]
  print(*ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    a, b = input().split()
    print(s[int(a)-1:int(b)].count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac = [0]*n
for i in range(n-1):ac[i+1] = ac[i] + (s[i:i+2]=="AC")
for i in range(q):
    l,r=map(int,input().split())
    print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

a=int(input())
b=input()
c=0
d=1000000

for i in range(a):
 c=0
 for j in range(a):
  if ((i<j and b[j]=="E")or(i>j and b[j]=="W")):
   c+=1
 d=min(d,c)


print(d)
   

### FIXED CODE ###

a=int(input())
b=input()
c=b.count('E')
d=0
e=c

for i in range(a):
 if b[i]=='E':
  c-=1
 else:
  d+=1
 e=min(e,c+d)


print(e)
### BUGGY CODE ###

import sys
from collections import Counter

n = int(input())
l_list = [2, 1]
i = 2

while True:
    l_list.append(l_list[i-1] + l_list[i-2])
    if len(l_list) - 1 == n:
        print(l_list[-1])
        sys.exit()
    i += 1


### FIXED CODE ###

import sys
from collections import Counter

n = int(input())
if n == 0:
    print(2)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()
l_list = [2, 1]
i = 2

while True:
    l_list.append(l_list[i-1] + l_list[i-2])
    if len(l_list) - 1 == n:
        print(l_list[-1])
        sys.exit()
    i += 1
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n, d = []):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      if i in d or not d:
        res.append(i)
      if i != n // i:
        if n // i in d or not d:
          res.append(n // i)
  return res

def isprime(n):
  for i in range(2, n+1):
    if i*i <= n:
      if (n % i == 0):
        return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  y = divi(b, x)
  cnt = 0
  for i, yy in enumerate(y):
    if not isprime(yy):
      continue
    cnt += 1
  print(cnt)
main()

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

def isprime(n):
  if n == 2:
    return True
  if n % 2 == 0 or n < 2:
    return False
  for i in range(3, int(n**0.5)+1, 2):
    if (n % i == 0):
      return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 1
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()
### BUGGY CODE ###

from itertools import count
 
N = int(input())
S = input()
 
abc = set(S)
 
T = {''}
 
flag = True
for i in count():
    T2 = set(T)
    T = set()
    for t in T2:
        for c in abc:
            if S.count(t + c) > 1:
                T.add(t + c)
                flag = False
    if flag:
        print(i)
        break
    flag = True

### FIXED CODE ###

N = int(input())
S = input()

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

s = input()
n = len(s) 
ls = [0]*2019
ls[0]+=1
for i in range(n):
  ls[int(s[i:]) % 2019] += 1

ans = 0
for a in ls:
  ans += a*(a-1)//2
print(ans)
       

### FIXED CODE ###



s = input()
n = len(s) 

rs = [1]*n
for i in range(1,n):
  rs[i] = rs[i-1]*10 %2019
  
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (rs[n-i-1])
  r %= 2019
  ls[r] += 1

ans = 0
for a in ls:
  ans += a*(a-1)//2
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    A.sort()

    ans = [0] * (10 ** 6 + 1)

    for a in A:
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            ans[a * i] += 1

    res = 0
    for a in A:
        if ans[a] == 0 or ans[a] == 1:
            res += 1

    print(res)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    ans = [0] * (10 ** 6 + 1)

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            ans[a * i] += 1

    res = 0
    c = collections.Counter(A)
    for a in A:
        if ans[a] == 0 and c[a] == 1:
            res += 1

    print(res)



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

N = int(input())
A = list(int(input())for i in range(N))
H = [float('inf'),A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        for j in range(len(H)-1,-1,-1):
            if H[j] >= A[i]:
                H[j+1] = A[i]
                break
print(len(H)-1)

### FIXED CODE ###

N = int(input())
A = list(int(input())for i in range(N))
H = [A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        l,r =0,len(H)
        while l != r :
            if H[(l+r)//2]>=A[i]:
                l = (l+r)//2+1
            else:
                r = (l+r)//2
        H[l] = A[i]
print(len(H))
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
As = list(map(int, stdin.readline().rstrip().split()))

nums = []
ans = 0

s = set(As)
s = list(s)


for i in range(len(s)):
    num = As.count(s[i])
    nums.append(num)
    p = num * (num-1) / 2
    ans += p

for k in range(n):
    num = nums[s.index(As[k])] - 1
    p = num*(num-1)/2
    bigp = (num+1)*num/2
    print(int(ans - bigp + p))


### FIXED CODE ###

import collections
from sys import stdin
n = int(stdin.readline().rstrip())
ass = list(map(int, stdin.readline().rstrip().split()))

c = collections.Counter(ass)

cnum =[0]*len(c)
keys = c.keys()

cs = {}
for i in keys:
    key = c[i]
    combi = key *(key-1) / 2
    cs[i] = combi

sum = sum(cs.values())

for i in range(n):
    add = c[ass[i]]-1
    adds = add *(add-1) / 2
    ans = sum - cs[ass[i]] + adds
    print(int(ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
sadlist = []
for h in range(n):
    a[h] = a[h] - (h + 1)
for i in a:
    sad = 0
    for j in range(n):
        sad = sad + abs(a[j] - i)
    sadlist.append(sad)
print(min(sadlist))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
if n % 2 == 0:
    print(sum(a[int(n / 2):]) - sum(a[:int(n / 2)]))
else:
    print(sum(a[int((n + 1) / 2):]) - sum(a[:int((n - 1) / 2)]))
### BUGGY CODE ###

N=int(input())
button=[]

for i in range(N):
  button.append(int(input()))

cnt=0
i=0

while True:
  i=button[i]-1 #←ここが理解できない。。。
  cnt+=1
  if i==1:
    print(cnt)
    break
  if cnt>N:
    print(-1)

### FIXED CODE ###

N=int(input())
a=[int(input()) for _ in range(N)]

btn=1
cnt=0

while True:
  btn=a[btn-1]
  cnt+=1
  if btn==2:
    print(cnt)
    break
  if cnt>N:
    print(-1)
    break
### BUGGY CODE ###

s=input()
count2=0
count=s.count("ABC")

while s.count("ABC")!=0:
    s=s.replace("ABC", "BCA")
    count2+=s.count("ABC")
print(count+count2)


### FIXED CODE ###

s=input()
n=0
c=0
i=0
while i<len(s):
  if s[i]=="A":
    c+=1
  elif s[i:i+2]=="BC":
    n+=c
    i+=1
  else:
    c=0
  i+=1
print(n)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = deque([(Dh, Dw)])
    while True:
        h, w = q.pop()
        # print('({}, {}) = {}'.format(h, w, ans))
        M[h][w] = ans
        if h == Ch and w == Cw:
            print(ans)
            return True
        for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= h+dh < H and 0 <= w+dw < W and M[h+dh][w+dw] == '.':
                q.append((h+dh, w+dw))
        if len(q) == 0:
            # for h in range(H):
            #     print(M[h])
            f = False
            for h in range(H):
                for w in range(W):
                    if M[h][w] != '.':
                        continue
                    for i, j in [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-2, 1), (-1, 1), (1, 1), (2, 1), (-2, 0), (2, 0), (-2, -1), (-1, -1), (1, -1), (2, -1), (-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2)]:
                        if 0 <= h+i < H and 0 <= w+j < W and M[h+i][w+j] == ans:
                            f = True
                            # print('warp to ({}, {})'.format(h, w))
                            q.append((h, w))
            if f:
                ans += 1
            else:
                print(-1)
                return True

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

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

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
for i in B:
    print(len([j for j in A if j == i]))
    while i in A:
        A.remove(i)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(range(1, N + 1))
import collections
new_A=collections.Counter(A)
for i in B:
    print(new_A[i])
### BUGGY CODE ###

# D - Coloring Edges on Tree

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

# 2次元配列で塗る色（頂点,遷移先の頂点）を管理する
C = [[0]*n for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[node][chi] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[a][b])

### FIXED CODE ###

# D - Coloring Edges on Tree
import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

C = {}

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[(node, chi)] = cid
            C[(chi, node)] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[(a,b)])
### BUGGY CODE ###

def main():
  N, M = list(map(int, input().split()))
  L = {}
  D = [[0, i] for i in range(N+1)]

  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    if Data[0] in L:
      L[Data[0]].append(Data[1])
    else:
      L[Data[0]] = [Data[1]]
    D[Data[1]][0] += 1

  for i in range(1, N+1):
    if D[i][0] == 0:
     s = D[i][1]
     break

  P = [[0, 0] for i in range(N + 1)]
  S = []
  t = L[s]
  for i in t:
    S.append(i)
    P[i] = [1, s]

  while True:
    if len(S) == 0:
      break
    j = S.pop()
    if j not in L:
      continue
    t = L[j]
    for i in t:
      if P[i][0] != 0:
        if P[i][0] < P[j][0] + 1:
          P[i] = [P[j][0] + 1, j]
          S.append(i)
      else:
        P[i] = [P[j][0] + 1, j]
        S.append(i)
  for i in P[1:]:
    print(i[1])

main()

### FIXED CODE ###

def main():
  N, M = list(map(int, input().split()))
  inN = [0 for i in range(N)]
  outN = [[] for i in range(N)]
  
  for i in range(N + M - 1):
    Data = list(map(int, input().split()))
    inN[Data[1] - 1] += 1
    outN[Data[0] - 1].append(Data[1] - 1)
  
  D = []
  for i in range(N):
    if inN[i] == 0:
      D.append(i)
      
  L = []
  while D != []:
    t = D.pop()
    L.append(t)
    for i in outN[t]:
      inN[i] -= 1
      if inN[i] == 0:
        D.append(i)
   
  Ans = [0 for i in range(N)]
  for i in L:
    for j in outN[i]:
      Ans[j] = i + 1
      
  for i in Ans:
    print(i)
main()
### BUGGY CODE ###

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


def count(N,A):

    for i in range(N):
        print(A.count(i+1))
        if i+1 in A:
            A.remove(i+1) 
count(N,A)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Ansbox = [0]*(N+1)

def count(N,A,Ansbox):

    for i in range(N- 1):
        Ansbox[A[i] - 1] += 1
        
    for i in range(N):
        print(Ansbox[i])
        
count(N,A,Ansbox)
### BUGGY CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SUM_A=[0 for _ in range(N+1)]
for i in range(N):
    SUM_A[i+1] = A[i] + SUM_A[i]

SUM_B=[0 for _ in range(M+1)]
for i in range(M):
    SUM_B[i+1] = B[i] + SUM_B[i]

cnt = 0
for i in range(N+1):
    for j in range(M+1):
        if SUM_A[i]+SUM_B[j] <= K:
            if i+j > cnt:
                cnt = i+j
        else:
            break
print(cnt)

### FIXED CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
SUM_A=[0 for _ in range(N+1)]
for i in range(N):
    SUM_A[i+1] = A[i] + SUM_A[i]
    if SUM_A[i+1] > K:
        N=i
        break

SUM_B=[0 for _ in range(M+1)]
for i in range(M):
    SUM_B[i+1] = B[i] + SUM_B[i]
    if SUM_B[i+1] > K:
        M=i
        break

cnt = N
for i in range(N+1)[::-1]:
    V=K-SUM_A[i]
    j = cnt-i
    while j < M+1 and SUM_B[j] <= V:
        j += 1
    j-=1
    if i+j > cnt:
        cnt = i+j
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
LIM = 10 ** 18
ans = 1
for i in A:
    ans *= i
if ans > LIM:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
LIM = 10 ** 18
ans = 1
if A[-1] == 0:
    print(0)
    exit()
for i in A:
    ans *= i
    if ans > LIM:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import heapq

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

INF = 10**7
dist = [[INF]*w for _ in range(h)]
dist[sh][sw] = 0
q = [(0,sh,sw)]
flag = 0
while q:
    
    d,vsh,vsw = heapq.heappop(q)
    
    for dh in range(-2,3):
        for dw in range(-2,3):
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if dh == 0 and dw==0: continue
            if s[newh][neww] == "#": continue
                
            if abs(dh)+abs(dw)==1:
                if dist[newh][neww] > d:
                    dist[newh][neww] = d
                    if newh == gh and neww == gw: flag
                    heapq.heappush(q,(d,newh,neww))
            else:
                if dist[newh][neww] > d+1:
                    dist[newh][neww] = d+1
                    heapq.heappush(q,(d+1,newh,neww))
    if flag: break
if dist[gh][gw] == INF: print(-1)
else: print(dist[gh][gw])

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

dist = [[-1]*w for _ in range(h)]
dist[sh][sw] = 0
q = deque([(0,sh,sw)])
warpq = deque([])

while q or warpq:
    while q:

        d,vsh,vsw = q.popleft()

        flag = 0
        
        for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if s[newh][neww] == "#":
                if flag ==0:
                    warpq.append((d,vsh,vsw))
                    flag = 1
                continue

            if dist[newh][neww] == -1:
                dist[newh][neww] = d
                q.append((d,newh,neww))

    while warpq:

        d,vsh,vsw = warpq.popleft()
        for dh in range(-2,3):
            for dw in range(-2,3):
                newh = vsh+dh
                neww = vsw+dw
                if newh<0 or h<=newh or neww<0 or w<=neww: continue
                if abs(dh)+abs(dw)<=0: continue
                if s[newh][neww] == "#": continue

                if dist[newh][neww] == -1:
                    dist[newh][neww] = d+1
                    q.append((d+1,newh,neww))
            
print(dist[gh][gw])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
maxA = max(A)
prv_ii = 0
cnt = 0
for i in range(1,maxA+1):
  try:
    ii = A[prv_ii:].index(i)
    cnt += 1
    prv_ii = ii + prv_ii + 1 
  except:
    break
print(N-cnt if cnt!=0 else -1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
maxA = max(A)
num = 0
for i in range(N):
  if A[i] == num+1:
    num += 1
print(N-num if num!=0 else -1)
### BUGGY CODE ###

import heapq

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

def solve(R_ite, L_ite, n):
	heapq.heapify(R_ite)
	heapq.heapify(L_ite)

	for _ in range(n):
		heapq.heappop(R_ite)
	for _ in range(N-n):
		heapq.heappop(L_ite)

	return sum(R_ite) + sum(L_ite)

ans = float("inf") * (-1)
for i in range(N+1):
	R = A[:N+i]
	LL = A[N+i:]
	L = [LL[j] * (-1) for j in range(len(LL))]

	ans = max(ans,solve(R,L,i))

print(ans)

### FIXED CODE ###

import heapq

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

pre = A[:N]
epi = A[2*N:]
epi = [epi[j]*(-1) for j in range(N)]
t_pre = sum(pre)
t_epi = sum(epi)

heapq.heapify(pre)
heapq.heapify(epi)

pre_sum = []
epi_sum = []

pre_sum.append(t_pre)

for i in range(N):
	t_push = A[N+i]
	heapq.heappush(pre, t_push)
	t_pop = heapq.heappop(pre)
	t_pre = t_pre + t_push - t_pop
	pre_sum.append(t_pre)


epi_sum.append(t_epi)

for i in range(N):
	t_push = A[-(N+i+1)] * (-1)
	heapq.heappush(epi, t_push)
	t_pop = heapq.heappop(epi)
	t_epi = t_epi + t_push - t_pop
	epi_sum.append(t_epi)

epi_sum = [epi_sum[-i] for i in range(1,N+2)]
ans = []

for i in range(N+1):
	ans.append(pre_sum[i]+epi_sum[i])

print(max(ans))