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

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
res = 0
for i in range(N-1,-1,-1):
  for j in range(N-1,i,-1):
    if S[i]==S[j]:
      dp[i][j]=max(dp[i+1][j+1]+1,dp[i][j])
    res = max(res,min(j-1,dp[i][j]))
print(res)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
res = 0
for i in range(N-1,-1,-1):
  for j in range(N-1,i,-1):
    if S[i]==S[j]:
      dp[i][j]=max(dp[i+1][j+1]+1,dp[i][j])
    res = max(res,min(j-i,dp[i][j]))
print(res)
### BUGGY CODE ###

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

for x in range(k,-1,-1):
    if s-x > k*2:
        break
    if s < x:
        continue
    for y in range(k,-1,-1):
        if s-x-y > k:
            break
        if s < x+y:
            continue
        for z in range(k,-1,-1):
            if s-x-y-z > 0:
                break
            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,-1):
    if s-x > k*2:
        break
    if s < x:
        continue
    for y in range(k,-1,-1):
        if s-x-y > k:
            break
        if 0<= s-x-y <=k:
            ans +=1

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

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


def main():
	Ls = []
	Rs = []
	for i in range(M):
		inputs = list(map(int,input().split()))
		Ls.append(inputs[0])
		Rs.append(inputs[1])

	result = set()
	for i in range(1, M + 1):
		Li = Ls[i - 1]
		LiPlus = { j for j in range(Li + 1, Rs[i - 1] + 1) }
		LiPlus.add(Li)

		if len(result) == 0:
			result = LiPlus
			continue
		result = result & LiPlus

	print(len(result))

if __name__ == '__main__':
	main()

### FIXED CODE ###

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


def main():
	Ls = []
	Rs = []
	for i in range(M):
		inputs = list(map(int,input().split()))
		Ls.append(inputs[0])
		Rs.append(inputs[1])

	maxL = max(Ls)
	minR = min(Rs)

	if maxL > minR:
		print(0)
	else:
		print(minR - maxL + 1)

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

from collections import deque

H, W = map(int, input().split())
A = list()
seen = set()
q = deque()
for i in range(H):
    s = input()
    for j, c in enumerate(s):
        if c == '#':
            q.append((i, j, 0))
            seen.add((i, j))
    A.append(s)

ans = 0
while len(q) > 0:
    i, j, x = q.popleft()
    ans = max(ans, x)
    if i > 0 and (i - 1, j) not in seen:
        q.append((i - 1, j, x + 1))
        seen.add((i - 1, j))
    if j > 0 and (i, j - 1) not in seen:
        q.append((i, j - 1, x + 1))
        seen.add((i, j - 1))
    if i < H - 1 and (i + 1, j) not in seen:
        q.append((i + 1, j, x + 1))
        seen.add((i + 1, j))
    if j < W - 1 and (i, j + 1) not in seen:
        q.append((i, j + 1, x + 1))
        seen.add((i, j + 1))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W = MI()
grid = [list(input()) for _ in range(H)]

seen = set()
q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j, 0))
            seen.add(i * W + j)
while len(q) > 0:
    h, w, d = q.popleft()
    for dh, dw in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if 0 <= h + dh < H and 0 <= w + dw < W and (h + dh) * W + w + dw not in seen:
            q.append((h + dh, w + dw, d + 1))
            seen.add((h + dh) * W + w + dw)
print(d)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

d = dict()
ans = 0
ss = [input() for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	#print(s)
	n = len(s)
	rh = RollingHash(s, BASE, MOD)
	if n == 1:
		ans += zero[ord(s[0])-97]
	else:
		suff = rh.get(1, n)
		if suff in d:
			ans += d[suff][ord(s[0])-97]
		alph = set()
		alph.add(ord(s[0])-97)
		for i in range(1, n-1):
			alph.add(ord(s[i])-97)
			tmp = rh.get(i+1, n)
			if tmp in d:
				for x in alph:
					d[tmp][x] += 1
			else:
				d[tmp] = [0 for _ in range(26)]
				for x in alph:
					d[tmp][x] += 1
		alph.add(ord(s[n-1])-97)
		for x in alph:
			zero[x] += 1
	#print(ans)
	#print(d, sep="\n")
print(ans)


### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

BASE, MOD = 1999849216943526259, (1<<61)-1

d = dict()
ans = 0
ss = [str(input())[2:-1][::-1] for _ in range(int(input()))]
zero = [0 for _ in range(26)]
ss.sort(key=lambda x: -len(x))
for s in ss:
	n = len(s)
	if n == 1:
		ans += zero[ord(s[n-1])-97]
	else:
		hashes = [0 for _ in range(n-1)]
		hashes[0] = ord(s[0])
		for i in range(1, n-1):
			hashes[i] = (hashes[i-1] * BASE + ord(s[i])) % MOD
		if hashes[n-2] in d:
			ans += d[hashes[n-2]][ord(s[n-1])-97]
		alph = [0 for _ in range(26)]
		alph[ord(s[n-1])-97] = 1
		for i in range(n-2, 0, -1):
			alph[ord(s[i])-97] = 1
			if hashes[i-1] not in d:
				d[hashes[i-1]] = [0 for _ in range(26)]
			for j, a in enumerate(alph):
				d[hashes[i-1]][j] += a
		alph[ord(s[0])-97] = 1
		for j, a in enumerate(alph):
			zero[j] += a
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
magic = []
for _ in range(n):
    magic += [list(map(int, input().split()))]
ans = [float('inf')]*(h+1)
ans[-1] = 0

for i in range(h, 0, -1):
    if ans[i] == float('inf'):
        continue
    else:
        for j in magic:
            if i-j[0] < 0:
                if ans[0] > ans[i]+j[1]:
                    ans[0] = ans[i]+j[1]
            elif ans[i-j[0]] > ans[i]+j[1]:
                ans[i-j[0]] = ans[i]+j[1]
print(ans[0])




### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###


n,k = map(int,input().split())
li = list(map(int,input().split()))

ans = [0]*n
ans[0] = 0

for i in range(1,n):
    l = []
    if k > i:
        for j in range(i):
            l.append(abs(li[i]-li[j])+ans[j])
    else:
        for j in range(1,k+1):
            l.append(abs(li[i]-li[i-j])+ans[i-j])
    # print(l)
    ans[i] = min(l)

print(ans[-1])

### FIXED CODE ###


n,k = map(int,input().split())
li = list(map(int,input().split()))

ans = [0]*n
# 地味に遅い
# for i in range(1,n):
#     l = []
#     if k > i:
#         for j in range(i):
#             l.append(abs(li[i]-li[j])+ans[j])
#     else:
#         for j in range(1,k+1):
#             l.append(abs(li[i]-li[i-j])+ans[i-j])
#     ans[i] = min(l)
# print(ans[-1])

for i in range(1,n):
    l = [ abs(li[i]-li[j]) + ans[j] for j in range(max(0,i-k),i)]
    # print(l)
    ans[i] = min(l)
print(ans[-1])
### BUGGY CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n,q=map(int,readline().split())
    stx = [[int(x) for x in readline().split()] for _ in range(n)]
    event=[]
    stop=set()
    for s,t,x in stx:
        event.append([s-x,1,x])
        event.append([t-x,-1,x])
    event.sort()
    d=[int(readline()) for _ in range(q)]

    k=0
    for i in range(q):
        while k<2*n and event[k][0]<=d[i]:
            if event[k][1]==1: stop.add(event[k][2])
            else: stop.remove(event[k][2])
            k+=1
        print(min(stop) if stop!=set() else -1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

# coding utf-8
import math
N, K = map(int, input().rstrip().split())

H = list(map(int, input().rstrip().split()))

if N > K:
    for i in range(K):
        H.remove(max(H))
    ans = sum(H)
else:
    ans = 0

print(ans)


### FIXED CODE ###

# coding utf-8
import math

N, K = map(int, input().rstrip().split())

H = list(map(int, input().rstrip().split()))
H.sort()

if N > K:
    if K == 0:
        ans = sum(H)
    else:
        ans = sum(H[:-K])
else:
    ans = 0

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

n = int(input())
a=list(map(int,input().split()))
j = 1
ans = list()
while j <= n:
    ans.append(a.index(j)+1)
    j = j+1
print(' '.join(map(str, ans)))


### FIXED CODE ###

n = int(input())
a=list(map(int,input().split()))
j = 1
ans = [0] * n
while j <= n:
    ans[a[j-1]-1] =  j
    j = j+1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

N, Q = list(map(int,input().split()))
S = input()
lr = []
for i in range(Q):
  lr.append(list(map(int,input().split())))

for i in lr:
  print(S[i[0]-1:i[1]].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
x = [0]*N
cnt = 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        cnt += 1
    x[i] = cnt

lr = []
for _ in range(Q):
    lr.append(map(int, input().split()))

for l, r in lr:
    print(x[r-1]-x[l-1])
### BUGGY CODE ###

(n, m, q) = map(int, input().split(" "))

ns = [[0 for _ in range(n + 1)]for _ in range(n + 1)]

for i in range(m):
    (l, r) = map(int, input().split(" "))
    ns[l][r] += 1

for i in range(q):
    count = 0
    (ql, qr) = map(int, input().split(" "))
    for j in range(ql, qr + 1):
        for k in range(j, qr + 1):
            count += ns[j][k]
    print(count)

### FIXED CODE ###

(n, m, q) = map(int, input().split(" "))

ns = [[0 for _ in range(n + 1)]for _ in range(n + 1)]

for i in range(m):
    (l, r) = map(int, input().split(" "))
    ns[l][r] += 1

for i in range(1, n + 1):
    for j in range(i, n + 1):
        ns[i][j] += ns[i][j - 1]
for j in range(1, n + 1):
    for i in range(1, j + 1):
        ns[i][j] += ns[i - 1][j]

for i in range(q):
    count = 0
    (l, r) = map(int, input().split(" "))
    print(ns[r][r] - ns[l - 1][r])
### BUGGY CODE ###

N=int(input())
num = input()
for _ in range(N+1):
    n = list(map(int, num.split()))

for i in range(N):
    for j in range(i, N):
        if n[i]-n[j]>1:
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

n=int(input())
h=[int(i) for i in input().split()]
f=1
h[0]-=1
for i in range(1,n):
    if h[i]-h[i-1]>=1:h[i]+=-1
    elif h[i]-h[i-1]==0:h[i]+=0
    else:
        f=0
        print("No")
        break
if f==1:print("Yes")
### BUGGY CODE ###

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

vs1 = [vs[i] for i in range(n) if i % 2 == 0]
vs2 = [vs[i] for i in range(n) if i % 2 != 0]

vsc1 = []
for v in set(vs1):
    vsc1.append((v, vs1.count(v)))

vsc2 = []
for v in set(vs2):
    vsc2.append((v, vs2.count(v)))

vsc1 = sorted(vsc1, key=lambda x: x[1], reverse=True)
vsc2 = sorted(vsc2, key=lambda x: x[1], reverse=True)
vsc1.append((-1, 0))
vsc2.append((-1, 0))

if vsc1[0][0] != vsc2[0][0]:
    print(n - (vsc1[0][1] + vsc2[0][1]))
else:
    print(n - max(vsc1[0][1] + vsc2[1][1], vsc1[1][1] + vsc2[0][1]))

### FIXED CODE ###

from collections import defaultdict

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

vsd1 = defaultdict(int)
for i in range(0, n, 2):
    vsd1[vs[i]] += 1

vsd2 = defaultdict(int)
for i in range(1, n, 2):
    vsd2[vs[i]] += 1

vsc1 = []
for k, v in vsd1.items():
    vsc1.append((k, v))

vsc2 = []
for k, v in vsd2.items():
    vsc2.append((k, v))

vsc1.append((-1, 0))
vsc2.append((-1, 0))
vsc1 = sorted(vsc1, key=lambda x: x[1], reverse=True)
vsc2 = sorted(vsc2, key=lambda x: x[1], reverse=True)

if vsc1[0][0] != vsc2[0][0]:
    print(n - (vsc1[0][1] + vsc2[0][1]))
else:
    print(n - max(vsc1[0][1] + vsc2[1][1], vsc1[1][1] + vsc2[0][1]))
### BUGGY CODE ###

from collections import deque

N=input()
A=[ input() for i in range(N) ] 

A.sort()

K=[]
K2=[]

if N%2==0:
	n=(N-2)/2
	for i in range(n):
		K.append(-2)
	K.append(-1)
	K.append(1)
	for i in range(n):
		K.append(2)
else:
	n=(N-2)/2

	## Pattern 1
	for i in range(n):
		K.append(-2)
	K.append(-1)
	K.append(-1)
	for i in range(n+1):
		K.append(2)
	## End

	## Pattern 2
	for i in range(n+1):
		K2.append(-2)
	K2.append(1)
	K2.append(1)
	for i in range(n):
		K2.append(2)
	## End

ans=0

t1=0
for x, y in zip(A,K):
	t1+=x*y

t2=0
for x, y in zip(A,K2):
	t2+=x*y


print max(t1,t2)


### FIXED CODE ###

import sys


N=input()
A=[  int(sys.stdin.readline()) for i in range(N) ] 

A.sort()

K=[]
K2=[]

if N%2==0:
	n=(N-2)/2
	K=[ -2 for i in range(n) ]+[-1,1]+[ 2 for i in range(n) ]
else:
	n=(N-2)/2

	## Pattern 1
	K=[ -2 for i in range(n) ]+[-1,-1]+[ 2 for i in range(n+1) ]
	## End

	## Pattern 2
	K2=[ -2 for i in range(n+1) ]+[1,1]+[ 2 for i in range(n) ]
	## End

ans=0

t1=0
for x, y in zip(A,K):
	t1+=x*y

t2=0
for x, y in zip(A,K2):
	t2+=x*y


print max(t1,t2)
### BUGGY CODE ###

n, y = list(map(int, input().split(' ')))
for ten_th in range(int(y / 10000), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(int(y / 5000), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        for th in range(int(y / 1000), -1, -1):
            if y == ten_th * 10000 + five_th * 5000 + th * 1000 and n == ten_th + five_th + th:
                print(' '.join(str(s) for s in [ten_th, five_th, th]))
                exit()
print('-1 -1 -1')
            

### FIXED CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        if (y - ten_th * 10000 - five_th * 5000) % 1000 == 0:
            th = int((y - ten_th * 10000 - five_th * 5000) / 1000)
            if n == ten_th + five_th + th:
                print('{} {} {}'.format(ten_th, five_th, th))
                exit()
print('-1 -1 -1')
### BUGGY CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
bag = [0 for _ in range(W+1)]
for w,v in a:
  for i in range(min(w,W+1),W+1)[::-1]:
    bag[i] = max(bag[i], bag[i-w] + v)
print(bag[W])  


### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])
for i in range(1, n + 2):
    print(mod_comb(n + 1, i) - mod_comb(x, (i - 1)))


### FIXED CODE ###

def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while 0 < n:
        if n & 1:
            res = (res * a) % mod
            n -= 1
        else:
            a = (a ** 2) % mod
            n //= 2
    return (res % mod)


def mod_inverse(a, mod=(10 ** 9 + 7)):
    return mod_rep_pow(a, (mod - 2))


def mod_comb(facts, facts_inverse, n, k, mod=(10 ** 9 + 7)):
    return (facts[n] * facts_inverse[k] * facts_inverse[n - k])


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])
mod = 10 ** 9 + 7
facts = [1] * (n + 2)
for i in range(0, n + 1):
    facts[i + 1] = (facts[i] * (i + 1) % mod)

facts_inverse = [1] * (n + 2)
facts_inverse[n + 1] = mod_inverse(facts[n + 1])
for i in range(n + 1, 0, -1):
    facts_inverse[i - 1] = (facts_inverse[i] * (i)) % mod

for i in range(1, n + 2):
    if x < (i - 1):
        print(mod_comb(facts, facts_inverse, (n + 1), i) % mod)
    else:
        print((mod_comb(facts, facts_inverse, (n + 1), i) - (mod_comb(facts, facts_inverse, x, (i - 1)))) % mod)
### BUGGY CODE ###

def lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return lucas(n-1) + lucas(n-2)

N = int(input())

print(lucas(N))

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize=None)
def lucas(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return lucas(n-1) + lucas(n-2)

N = int(input())

print(lucas(N))
### BUGGY CODE ###

N = int(raw_input())
lis = []
count = 0
for i in xrange(N):
	num = int(raw_input())
	if num in lis:
		lis.remove(num)
		count -= 1
	else:
		lis.append(num)
		count += 1
print count

### FIXED CODE ###

from collections import Counter
N = int(raw_input())
lis = []
for i in xrange(N):
	lis.append(int(raw_input()))
lis.sort()
lister = dict(Counter(lis)).items()
count = 0
for item in lister:
	if item[1] % 2 == 1:
		count += 1
print count
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    ans = 0
    for j in range(i, n):
        ans += a[j]
        if ans == 0:
            count += 1
print(count)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
maze = [input() for _ in range(H)]

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.appendleft((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

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



while len(S)!=1:
    
    S.sort()
    
    if S[1]%S[0]==0:
        S.pop(1)
    
    else:
        S[1]=S[1]%S[0]

    if S[0]==1:
        print(1)
        exit()
print(S[0])

### FIXED CODE ###

import math

N=int(input())
S=list(map(int,input().split()))
F=S[0]
for i in range(N-1):
    F=math.gcd(F,S[i+1])

print(F)
### BUGGY CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                count += 1
print(count)

### FIXED CODE ###

K,S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i -j
        if 0 <= k <= K: 
            count += 1
print(count)
### BUGGY CODE ###

N,A,B =map(int,input().split())
D =[]
for i in range(N):
    for j in range(A):
        D.append("A")
    for k in range(B):
        D.append("B")

#print(D)

F =D[0:N]
#print(F)
print(F.count("A"))


### FIXED CODE ###

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

v = N//(A+B)
z = N %(A+B)

if z < A:
    print(A*v + z)
else:
    print(A*v + A)
### BUGGY CODE ###

import collections
N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))
def taikaku(A):
    n = len(A)
    A2 = []
    for i in range(n):
        p = []
        for j in range(n):
            p.append(A[j][i])
        A2.append(p)
    return(A == A2)
ans = 0
for i in range(N):
    if taikaku(S[i:]+S[:i]):
        ans += N
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))
def taikaku(A):
    n = len(A)
    b = True
    for i in range(n):
        for j in range(i+1):
            if A[j][i] != A[i][j]:
                b = False
                break
        if not b:
            break
    return(b)
ans = 0
for i in range(N):
    if taikaku(S[i:]+S[:i]):
        ans += N
print(ans)