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

AB = input().split(' ')
A = int(AB[0])
B = int(AB[1])
 
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            flag = True
            for c in cf:
                if i%c == 0:
                    #print(i,c,'flag is off')
                    flag = False
                    break
            if flag:
                cf.append(i)
    return cf
 
def check_cf(x1,x2):
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            return False
    return True
candidate = cf(A,B)
'''
decided_list = [candidate[0]]
 
for i in range(1,len(candidate)):
    flag = True
    for s in range(2,candidate[i]):
        if candidate[i]%s == 0:
            flag = False
            break
    if flag:
        decided_list.append(candidate[i])
'''
#print(candidate)
print(len(candidate)+1)

### FIXED CODE ###

AB = input().split(' ')
A = int(AB[0])
B = int(AB[1])
'''
def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
                cf.append(i)
    return cf
 
def check_cf(x1,x2):
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            return False
    return True
candidate = cf(A,B)
'''
'''
decided_list = [candidate[0]]
 
for i in range(1,len(candidate)):
    flag = True
    for s in range(2,candidate[i]):
        if candidate[i]%s == 0:
            flag = False
            break
    if flag:
        decided_list.append(candidate[i])
'''
#print(candidate)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def gcd(num1: int, num2: int) -> int:
    if num2 == 0:
        return num1
    else:
        return gcd(num2,num1%num2)
max_gcd = gcd(A,B)
result = factorization(max_gcd)
#print(result)
if len(result) == 1 and result[0][0] == 1:
    print(1)
else:
    print(len(result)+1)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
num = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            num += gcd(a,b,c)

print(num)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
num = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
          x = gcd(a,b,c)
          bai = sum([a==b,b==c,a==c])
          if bai == 0:
            num += x*6
          elif bai == 1:
            num += x*3
          else:
            num += x
            
print(num)
### BUGGY CODE ###

S = input().strip()
Sb = [c == "B" for c in S]

def reverse(Sb,i):
    _list = Sb.copy()
    _list[i] = not _list[i]
    return _list

def operate(Sb):
    _list = Sb.copy()
    cnt = 0
    while True:
        for i in range(len(_list)-1):
            if _list[i] and not _list[i+1]:
                cnt += 1
                _list = reverse(_list,i)
                _list = reverse(_list,i+1)
                break
        else:
            break
    return cnt
  
print(operate(Sb))

### FIXED CODE ###

S = input().strip()

w_total = 0
num_op = 0
for i,c in enumerate(S):
    if c == "W":
        w_total += 1
        num_op += i + 1 - w_total
        
print(num_op)
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [i-1 for i in A]
sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

### FIXED CODE ###

import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)
### BUGGY CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N=int(input())
A = [list(map(lambda x:int(x)-1,input().split())) for _ in [0]*N]

Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
Eb = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        Eb[k1].append(k0)
Ef = {k:set(v) for k,v in Ef.items()}
Eb = {k:set(v) for k,v in Eb.items()}

q = [k for k in Eb if Eb[k] == set()]
ans = 0
while q:
    qq = set()
    for k in q:
        for k2 in Ef[k]:
            qq.add(k2)
            Eb[k2].remove(k)
        Ef[k] = set()
    q = [k for k in qq if not Eb[k]]
    ans += 1
if sum(len(v) for v in Eb.values())>0 : ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
han=0
kot=0
i=0
if B-1>=N:
    print(math.floor(A*N/B)-A*math.floor(N/B))
    i=1
else:
    for a in range(B-1,N,5*B):
        if han<(math.floor(A*a/B)-A*math.floor(a/B)):
            han=(math.floor(A*a/B)-A*math.floor(a/B))
            kot=a

if i==0:
    print(han)

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
han=0
kot=0
i=0
if B==1:
    print(0)
    exit()
if B-1>=N:
    print(math.floor(A*N/B)-A*math.floor(N/B))
    i=1
else:
    for a in range(B-1,N,B):
        if han<(math.floor(A*a/B)-A*math.floor(a/B)):
            han=(math.floor(A*a/B)-A*math.floor(a/B))
            kot=a

if i==0:
    print(han)
### BUGGY CODE ###

# calculate N!(modP)
def fac(n):
    ans = 1
    mod = 10**9+7
    for i in range(1, n+1):
        ans *= i
        ans %= mod
    return ans
 
# calculate a**b(modP)     
def cal(a, b, mod):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return cal(a, b//2, mod)**2 % mod
    else:
        return (a * cal(a, b-1, mod)) % mod 
    
H, W, A, B = map(int, input().split())

ans = 0
mod = 10**9+7


for w in range(B, W):
    now = fac((H-A-1)+w) * cal(fac(H-A-1), mod-2, mod) * cal(fac(w), mod-2, mod) % mod
    now *= fac((A-1)+(W-w-1)) * cal(fac(A-1), mod-2, mod) * cal(fac(W-w-1), mod-2, mod) % mod
    ans = (ans+now) % mod
print(ans)

### FIXED CODE ###

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

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N

# 階乗
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 
# 逆元
inv[N - 1] = pow(fac[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
    ans %= MOD
    
print(ans % MOD)
### BUGGY CODE ###

from copy import deepcopy
def main():
    h, n = map(int, input().split())
    magics = [tuple(map(int, input().split())) for _ in range(n)]

    inf = float('inf')
    dp = [inf] * (h + 1)
    dp[0] = 0
    for magic in magics:
        dp_c = deepcopy(dp)
        for i1 in range(h + 1):
            if i1 <= magic[0]:
                dp[i1] = min(magic[1], dp_c[i1])
            else:
                dp[i1] = min(dp_c[i1], dp[i1 - magic[0]] + magic[1])
    print(dp[h])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

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

n=int(input())
a=[int(i) for i in input().split()]
ans=1
for i in a:
    ans *= i
if ans > 10 ** 18:
    ans = -1
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
ans=1
if 0 in a:
    ans = 0
else:
    for i in a:
        ans *= i
        if ans > 10 ** 18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]


ans = 0
for i in b:
    count_a = 0
    count_c = 0
    for j in range(n):
        if i > a[j]:
            count_a += 1
        if i < c[j]:
            count_c += 1
    ans += count_a * count_c
print(ans)

### FIXED CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

import bisect
count = 0
for i in b:
    a_count = bisect.bisect_left(a, i)
    c_count = n - bisect.bisect_right(c, i)
    count += a_count * c_count
    
print(count)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import numpy
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# めちゃくちゃ遅くて TLE
#V = [[0]*N for _ in range(N)]
#
#for i in range(N-1):
#    u,v,w = list(map(int, input().split()))
#    V[u-1][v-1] = w

U = numpy.array([0]*N, dtype=numpy.int32)
V = numpy.array([0]*N, dtype=numpy.int32)
W = numpy.array([0]*N, dtype=numpy.int32)

for i in range(N-1):
    u,v,w = list(map(int, input().split()))
    U[i] = u-1
    V[i] = v-1
    W[i] = w

D = dijkstra(csr_matrix((W,(U,V)), shape=(N,N)), directed=False, indices=0)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    childsof[u].append((v,w))
    childsof[v].append((u,w))

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)
### BUGGY CODE ###

K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)

cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp

### FIXED CODE ###

K = int(input())
a = ['1','2','3','4','5','6','7','8','9']
if K <= 9:
    print(K)
    exit()


cnt = 9
while True:
    a_tmp = []
    for s in a:
        for t in range(max(0, int(str(s[-1])) - 1), min(9, int(str(s[-1])) + 1) + 1):
            a_tmp.append(s+str(t))
            cnt += 1
            if cnt == K:
                print(s+str(t))
                exit()
    a = a_tmp
### BUGGY CODE ###

import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            # print(i)
            for j in range(i + 1, len(S) + 1):
                if len(d) > K and d[-1] < S[i:j]:
                    break
                if S[i:j] not in d:
                    bisect.insort(d, S[i:j])
                    d = d[:K]
        if len(d) >= K:
            break
    # print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    # S = [random.choice('abcdefghijklmnopqrstu') for _ in range(5000)]
    print(slv(S, K))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def slv(S, K):
    d = set([])
    for i in range(len(S)):
        for j in range(i + 1, i + 1 + K):
            d.add(S[i:j])

    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    # K = 3
    # S = ''.join([random.choice('abcdefghijklmnopqrstu') for _ in range(5000)])
    print(slv(S, K))


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

N, M = map(int, input().split())
mod = 10**9 + 7
num = abs(N - M)

if num > 1:
    print(0)
    exit()

n = 1
for i in range(1, N+1):
    n *= i

if N == M:
    m = n
    ans = (2 * n * m) % mod
else:
    if N < M:
        m = M * n
    else:
        m = n // N
    ans = (n * m) % mod

print(ans)

### FIXED CODE ###

import math

N, M = map(int, input().split())
mod = 10**9 + 7

if abs(N - M) > 1:
    print(0)
    exit()

n = math.factorial(N)
if N == M:
    m = n
    ans = (2 * n * m) % mod
else:
    if N < M:
        m = M * n
    else:
        m = n // N
    ans = (n * m) % mod

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


from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    res%=mod
print(res)



### FIXED CODE ###


from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    #res%=mod
print(res%mod)
### BUGGY CODE ###

N = int(input())
count = 0
gacha = []

for i in range(N):
    tmp = input()
    if tmp in gacha:
        continue
    else:
        count += 1
        gacha.append(tmp)
        

print(count)

### FIXED CODE ###

import collections
N = int(input())

gacha = collections.deque()

for i in range(N):
    gacha.append(input())
   
print(len(collections.Counter(gacha)))
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
    a = int(input())
    if a in l:
        l.remove(a)
    else:
        l.append(a)
print(len(l))


### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
    a = int(input())
    if a in d:
        d[a] = 1 - d[a]
    else:
        d[a] = 1
print(sum(d.values()))
### BUGGY CODE ###

h,w=map(int,input().split())
field=[0]+["#"+input()+"#" for i in range(h)]+[0]
field[0],field[-1]="#"*(w+2),"#"*(w+2)
l,r,u,d=[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="#":continue
    l[i][j]=l[i][j-1]+1
    u[i][j]=u[i-1][j]+1
for i in range(1,h+1)[::-1]:
  for j in range(1,w+1)[::-1]:
    if field[i][j]=="#":continue
    r[i][j]=r[i][j+1]+1
    d[i][j]=d[i+1][j]+1
ans=0
for i in range(h+2):
  for j in range(w+2):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if c>ans:ans=c
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
field=[0]+["#"+input()+"#" for i in range(h)]+[0]
field[0],field[-1]="#"*(w+2),"#"*(w+2)
l,r,u,d=[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)],[[0 for i in range(w+2)] for i in range(h+2)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="#":continue
    l[i][j]=l[i][j-1]+1
    u[i][j]=u[i-1][j]+1
for i in range(1,h+1)[::-1]:
  for j in range(1,w+1)[::-1]:
    if field[i][j]=="#":continue
    r[i][j]=r[i][j+1]+1
    d[i][j]=d[i+1][j]+1
ans=0
for i in range(h+2):
  for j in range(w+2):
    c=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3
    if c>ans:ans=c
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 10**6
for i in range(len(s)):
    x = s[:i]
    y = s[i+1:len(s)]
    ans = min(ans,x.count("W")+y.count("E"))
print(ans)

### FIXED CODE ###

import numpy
n = int(input())
s = input()
a = [0]*n
ans = 10**6
for i in range(n):
    if s[i] == 'W':
        a[i] = 1
res = numpy.cumsum(a)
for i in range(n):
    x = res[i]-str(a[i]).count('1')
    y = n-i-1-(res[n-1]-res[i])
    ans = min(ans,x+y)
print(ans)
### BUGGY CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                que.append([ny, nx])
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

dy = [1, 0]
dx = [0, 1]

print(bfs())

### FIXED CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    que = deque()
    que.append([0, 0])
    if s[0][0] == '#':
        d[0][0] = 1
    else:
        d[0][0] = 0

    while que:
        p = que.popleft()
        if p[0] == h-1 and p[1] == w-1:
            break

        for i in range(2):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[p[0]][p[1]] == '.' and  s[ny][nx] == '#':
                    if d[ny][nx] > d[p[0]][p[1]]+1:
                        d[ny][nx] = d[p[0]][p[1]]+1
                        que.append([ny, nx])
                else:
                    if d[ny][nx] > d[p[0]][p[1]]:
                        d[ny][nx] = d[p[0]][p[1]]
                        que.append([ny, nx])

    return d[h-1][w-1]

h, w = MAP()
s = [input() for i in range(h)]
d = [[inf]*w for i in range(h)]

dy = [1, 0]
dx = [0, 1]

print(bfs())
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                ans += 1

print(ans)


### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            ans += 1

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

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ab=[]
for i in range(N):
  for j in range(N):
    s=a[i]+b[j]
    if s in ab:
      ab.remove(s)
    else:
      ab.append(s)

ans=ab[0]
for i in range(1,len(ab)):
  ans^=ab[i]
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
bits=[[] for i in range(29)]
for i in range(29):
  mod = 2**(i+1)
  for j in b:
    bits[i].append(j%mod)
  bits[i].sort()

ans = 0
for k in range(29):
  al = []
  cnt = 0
  mod = 2**k
  for i in a:
    al.append(i%(2*mod))
  al.sort(reverse=True)
  r1 = r2 = r3 = 0
  for j in al:
    while r1 < N and bits[k][r1]+j < mod:
      r1 += 1
    while r2 < N and bits[k][r2]+j < 2*mod:
      r2 += 1
    while r3 < N and bits[k][r3]+j < 3*mod:
      r3 += 1
    cnt += N-r3+r2-r1
  ans += (cnt%2) << k
print(ans)