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

from itertools import combinations


def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    for candidate in combinations(XYs, r=K):
        candidate = list(candidate)
        xs = sorted([x for x, y in candidate])
        max_x = xs[-1]
        min_x = xs[0]
        ys = sorted([y for x, y in candidate])
        max_y = ys[-1]
        min_y = ys[0]

        ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))


### FIXED CODE ###


def solve(N, K, XYs):
    ans = 10 ** 19 + 1

    XYs.sort(key=lambda x: x[0])
    for i in range(N):
        for j in range(i+K-1, N):
            narrowedXY = XYs[i:j+1]
            narrowedXY.sort(key=lambda x: x[1])
            for y1 in range(len(narrowedXY)):
                for y2 in range(y1+K, len(narrowedXY)+1):
                    min_x = XYs[i][0]
                    max_x = XYs[j][0]
                    ys = [xy[1] for xy in narrowedXY[y1:y2]]
                    max_y = max(ys)
                    min_y = min(ys)
                    ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))
### BUGGY CODE ###

x,y = map(int,input().split())
count = 1
counts = []
an = 0

for i in range(x,y+1):
  an = i
  for j in range(i+1,y+1):
    
    if j % an == 0:
      count += 1
      an = j
  counts.append(count)
  count = 0
  
print(max(counts))

### FIXED CODE ###

x,y = map(int,input().split())
an = x
count = 0
while an <= y:
    an *= 2
    count += 1

print(count)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
ans=0
for i in range(1,n+1):
  c=math.floor(a*i/b)-a*math.floor(i/b)
  ans=max(ans,c)
print(ans)

### FIXED CODE ###

import math
a,b,n=map(int,input().split())
ans=0
if b>n:
  ans=math.floor(a*n/b)
else:
  
  ans=math.floor(a*(b-1)/b)
print(ans)
### BUGGY CODE ###

def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return x!=1

dic={}
n=int(input())
i=2
if isprime(n):
    print(1)
    exit()
while n>1:
    if n%i==0:
        cnt=0
        if isprime(i):
            while n%i==0:
                cnt+=1
                n//=i
        dic[i]=cnt
        # cnt=0
        # if isprime(n//i):
        #     while n%(n//i)==0:
        #         cnt+=1
        #         n//=(n//i)
        #     dic[n//i]=cnt
    i+=1
ans=0
for i in dic:
    x=dic[i]
    r=(-1+(1+8*x)**0.5)//2
    ans+=r
print(int(ans))




### FIXED CODE ###

def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return x!=1


dic={}
n=int(input())
t=int(n**0.5)+1
for i in range(2,t):
    cnt=0
    while n%i==0:
        cnt+=1
        n//=i
    dic[i]=cnt
if n!=1:
    dic[n]=1
ans=0
for i in dic:
    x=dic[i]
    r=(-1+(1+8*x)**0.5)//2
    ans+=r
print(int(ans))
### BUGGY CODE ###

import sys

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A, B, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N - 1)]))
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))

graph = coo_matrix((C, (A, B)), shape=(N + 1, N + 1))
dists = dijkstra(graph.tocsr(), indices=K, directed=False)

for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))


### FIXED CODE ###

import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
ABC = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, sys.stdin.readline().split()))
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(Q)]))


def dijkstra(graph, start):
    """
    TODO: start していしなかったときに全部の距離を知りたい

    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in ABC:
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = dijkstra(graph, K)

for x, y in zip(X, Y):
    print(int(dists[x] + dists[y]))
### BUGGY CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [] #L[i][j]はi,j間の最短距離(i<=j)
for i in range(N):
  L.append([10**4 for j in range(N-i)])
for i in range(N):
  L[i][0] = 0
  if i < N-1:
    L[i][1] = 1
L[X-1][Y-X] = 1
for k in range(1,N):
  a = 0
  for i in range(N):
    for j in range(N-i):
      if L[i][j] == k:
        a += 1
      elif L[i][j] > k:
        for p in range(N):
          if p < i:
            if L[p][i-p] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[p][i-p] + L[p][i+j-p]
          elif p < i+j:
            if L[i][p-i] + L[p][i+j-p] < L[i][j]:
              L[i][j] = L[i][p-i] + L[p][i+j-p]
          else:
            if L[i][p-i] + L[i+j][p-i-j] < L[i][j]:
              L[i][j] = L[i][p-i] + L[i+j][p-i-j]
  print(a)


### FIXED CODE ###

[N,X,Y] = [int(s) for s in input().rstrip().split(' ')]
L = [0 for n in range(N)]
for i in range(N):
  for j in range(N-i):
    L[min(j,abs(X-1-i)+abs(Y-1-i-j)+1,abs(X-1-j-i)+abs(Y-1-i)+1)]+=1
for k in range(1,N):
  print(L[k])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
C - Unification
https://atcoder.jp/contests/abc120/tasks/abc120_c

"""
import sys
import re


def my_sub(m):
    len1 = len(m.group(1))
    len2 = len(m.group(2))
    if len1 > len2:
        return m.group(1)[0] * (len1 - len2)
    return m.group(2)[0] * (len2 - len1)


def solve(S):
    orig_len = len(S)
    while True:
        t = re.sub(r'(0+)(1+)', my_sub, S)
        t = re.sub(r'(1+)(0+)', my_sub, t)
        if t == S:
            break
        S = t
    return orig_len - len(S)


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
C - Unification
https://atcoder.jp/contests/abc120/tasks/abc120_c

"""
import sys


def solve(S):
    orig_len = len(S)
    num_value = {'0': -1, '1': 1}
    status = 0

    for s in S:
        status += num_value[s]
        #if s == '0':
        #    status -= 1
        #else:
        #    status += 1
    return orig_len - abs(status)


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    import sys

    sys.setrecursionlimit(10 ** 6)

    def dfs(now: int, depth: int):
        """深度を記録しながらDFS"""
        if depth >= N:
            return
        seen[now] = True
        temp_dis[now] = min(temp_dis[now], depth)
        for next in G[now]:
            dfs(next, depth + 1)
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)
    # print(G)

    distance = [set() for _ in [0] * N]
    for i in range(N):
        seen = [False] * N
        temp_dis = [N] * N
        dfs(i, 0)
        # print(i, temp_dis)
        for j in range(N):
            distance[temp_dis[j]].add((i, j) if i <= j else (j, i))
    
    for ans in distance[1:]:
        print(len(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    from collections import deque
        
    N, X, Y = map(int, input().split())

    G = [[1]] + [[x - 1, x + 1] for x in range(1, N - 1)] + [[N - 2]]
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)

    dist = [[-1] * N for _ in [0] * N]
    for s in range(N):
        q = deque([s])
        dist[s][s] = 0
        while q:
            v = q.popleft()
            for nv in G[v]:
                if dist[s][nv] == -1:
                    dist[s][nv] = dist[s][v] + 1
                    q.append(nv)
    res = [0] * N
    for i in range(N):
        for j in range(i + 1, N):
            res[dist[i][j]] += 1
    for d in range(1, N):
        print(res[d])


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

k=int(input())
import fractions
sum_g=0
for p in range(1,k+1):
    for q in range(1,k+1):
        for r in range(1,k+1):
            ans=p
            ans = fractions.gcd(ans, q)
            ans = fractions.gcd(ans, r)
            sum_g+=ans
            ans=0
print(sum_g)

### FIXED CODE ###

import math

K=int(input())
sum=0


for i in range(1,K+1):
    for j in range(1,K+1):
        a=math.gcd(i,j)
        for k in range(1,K+1):
            b=math.gcd(a, k)
            sum = sum + b

print(sum)
### BUGGY CODE ###

import sys
k=int(input())
A=[0]*k
C=[7%k]
A[7%k]=1
if 7%k==0:
    print(1)
    sys.exit()
while True:
    now=(C[-1]*10+7)%k
    C.append(now)
    if now==0:
        print(len(C))
        break
    if A[now]:
        print(-1)
        break

### FIXED CODE ###

import sys
k=int(input())
A=[0]*k
C=[7%k]
A[7%k]=1
if 7%k==0:
    print(1)
    sys.exit()
while True:
    now=(C[-1]*10+7)%k
    if A[now]==1:
        print(-1)
        break
    A[now]=1
    C.append(now)
    if now==0:
        print(len(C))
        break
### BUGGY CODE ###

import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    length = [[0 for i in range(b+1)] for j in range(a+1)]

    for i in range(a):
        e1 = seq1[i]
        tmp = length[i]
        for j in range(b):
            if e1 == seq2[j]:
                length[i+1][j+1] = tmp[j] + 1
            else:
                length[i+1][j+1] = max(tmp[j+1], length[i+1][j])
    return length[a][b]

n = input()
for i2 in range(n):
    seq1 = raw_input()
    seq2 = raw_input()

    print longestcommonsubsequence(seq1, seq2)

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

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

ans = []

for i in range(a):
    b = lis[i]
    c = ans.count(b)
    if c == 0:
        ans.append(b)

if len(ans) == a:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

ans = list(set(lis))

if a == len(ans):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import re
s = input()
ans = 0

s = s.replace("BC","D")
t = re.split("[BC]",s)
t = [x for x in t if x]
#print(s)
#print(t)

for e in t:
    ind=[i for i, x in enumerate(e) if x == 'A']
    #print(ind)
    for j in ind:
        srt = e[j+1:]
        ans+=srt.count("D")

print(ans)


### FIXED CODE ###

s = input()
s = s.replace("BC", "D")
#print(s)

ans = 0
cnt_a = 0
for i in range(len(s)):
    if s[i] in ["B", "C"]:
        cnt_a = 0
    elif s[i] == "A":
        cnt_a += 1
    elif s[i] == "D":
        ans += cnt_a

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

from math import *
from functools import reduce
def lcm(a,b):
  return a*b//gcd(a,b)
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=reduce(lcm,a)
ans=0
for i in a:
  ans+=c//i%mod
  ans%=mod
print(ans)

### FIXED CODE ###

from math import gcd
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=a[0]
for i in a[1:]:
  c=c*i//gcd(c,i)
ans=0
c%=mod
for i in a:
  ans+=c*pow(i,mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

mod = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(61):
    cnt_0 = 0
    cnt_1 = 0
    for j in range(N):
        if (A[j] >> i & 1):
            cnt_1 += 1
        else:
            cnt_0 += 1
    ans += (cnt_1 * cnt_0 * (2**i)) % mod
print(ans % mod)

### FIXED CODE ###

import numpy as np
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A = np.array(A, dtype = np.int64)
tmp = 0
for i in range(61):
    tmp_1 = np.count_nonzero(A & 1)
    tmp += ((tmp_1)*(N - tmp_1)*(2**i)) % mod
    A = A >> 1
print(tmp % mod)
### BUGGY CODE ###

red, green, blue, n = map(int, input().split())

ans = 0
for i in range(n // red + 1):
    for j in range(n // blue + 1):
        k = n - red * i - blue * j
        
        if k % green != 0 or k < 0:
            continue
        
        ans += 1

print(ans)

### FIXED CODE ###

red, green, blue, n = map(int, input().split())

ans = 0
for i in range(n // red + 1):
    for j in range(n // blue + 1):
        k = n - red * i - blue * j
        
        if k % green != 0 or k < 0:
            continue
        
        ans += 1

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

from collections import Counter

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

a = list(set(A))
cc = Counter(A)
dup = [x for x in a if A.count(x) > 1]
m = len(a)
l = len(A) 
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)

for k in A:
    if k not in dup:
        print(int(al))
    else :
        print(int(al-cc[k]+1))

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
a = list(set(A))
cc = Counter(A)
dup = set([x for x in a if cc[x] > 1])
c_l = [(cc[i]-1)*(cc[i])/2 for i in a]
al = sum(c_l)

# for k in A:
#     if k in dup:
#         print(int(al-cc[k]+1))
#     else :
#         print(int(al))
[print(int(al-cc[k]+1)) if k in dup else print(int(al)) for k in A]
### BUGGY CODE ###

s=input()
q=int(input())

for _ in range(0,q):
  n=input()
#  print(n[0:1])
  if n[0:1]=="1":
#    print("!")
    s = s[::-1]
  else:
    m=n.split()
    x=[]
    if m[1]=="1":
      x.append(m[2])
      x.append(s)
      s=''.join(x)
#      s=m[2]+s
    else:
      x.append(s)
      x.append(m[2])
      s=''.join(x)
#      s=s+m[2]
print(s)
      

### FIXED CODE ###

s=input()
q=int(input())

rev=1

sf=""
sb=s

for _ in range(0,q):
  n=input().split()
  if n[0]=="1":
    rev*=-1
  else:
    if (n[1]=="1" and rev==1) or (n[1]=="2" and rev==-1):
      sf+=n[2]
    else:
      sb+=n[2]

s=sf[::-1]+sb

if rev==1:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

s = input()
K = int(input())
n = len(s)

x = dict()
y = []
for i in range(5000):
    y.append([])

#O(N^2)
"""
for i in range(n):
    t = ""
    for j in range(i,n):
        t += s[j]
        if len(t) in x:
            if t not in y[len(t)]:
                y[len(t)].append(t)
        else:
            x[len(t)] = t
            y[len(t)].append(t)
X = []
for i in range(5000):
    if len(y[i]) == 0:
        continue
    y[i].sort()
    for j in range(len(y[i])):
        X.append(y[i][j])
"""
for i in range(n):
    t = ""
    for j in range(i,n):
        t += s[j]
        x[t] = t
X = []
for i in x:
    X.append(i)
X.sort()


#print(X)
print(X[K-1])

### FIXED CODE ###

s = input()
K = int(input())
n = len(s)

x = dict()
y = []
for i in range(5000):
    y.append([])

#O(N^2)
"""
for i in range(n):
    t = ""
    for j in range(i,n):
        t += s[j]
        if len(t) in x:
            if t not in y[len(t)]:
                y[len(t)].append(t)
        else:
            x[len(t)] = t
            y[len(t)].append(t)
X = []
for i in range(5000):
    if len(y[i]) == 0:
        continue
    y[i].sort()
    for j in range(len(y[i])):
        X.append(y[i][j])
"""
for i in range(n):
    t = ""
    for j in range(i,i+1+K):
        if j > (n-1):
            break
        t += s[j]
        x[t] = t
X = []
for i in x:
    X.append(i)
X.sort()


#print(X)
print(X[K-1])
### BUGGY CODE ###

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

ans = float('inf')
for xi in range(N - 1):
    for xj in range(xi + 1, N):
        for yi in range(N - 1):
            for yj in range(yi + 1, N):
                x1 = min([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                x2 = max([P[xi][0], P[xj][0], P[yi][0], P[yj][0]])
                y1 = min([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                y2 = max([P[xi][1], P[xj][1], P[yi][1], P[yj][1]])
                if x1 == x2 or y1 == y2:
                    continue

                cnt = 0
                for k in range(N):
                    x3, y3 = P[k]
                    if x1 <= x3 <= x2 and y1 <= y3 <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min(ans, (x2 - x1) * (y2 - y1))

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
P.sort()

ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K + 1):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

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

n, m = map(int, input().split())
xyz = [tuple(map(int, input().split())) for _ in range(n)]
def isum(i, x, y, z):
    s = 0
    s += x if (i>>0)&1 else -x
    s += y if (i>>1)&1 else -y
    s += z if (i>>2)&1 else -z
    return s

ans = 0
for i in range(2**3):
    dp = [[0, 0, 0] for _ in range(m+1)]
    for k in range(n):
        x, y, z = xyz[k]
        ndp = [[0, 0, 0] for _ in range(m+1)]
        for j in range(1, m+1):
            # iを含める場合は、一つ前のj-1から
            # iを含めない場合は、一つ前のjから
            xj, yj, zj = dp[j-1]
            inc = [xj+x, yj+y, zj+z]
            sj_1 = isum(i, *inc)

            noinc = dp[j]
            noinc_sum = isum(i, *noinc)
            if sj_1 > noinc_sum:
                ndp[j] = inc
            else:
                ndp[j] = noinc
        dp = ndp
    ans = max(ans, isum(i, *dp[-1]))
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
xyz = [tuple(map(int, input().split())) for _ in range(n)]
ans = 0
from itertools import product
for p in product([-1, 1], repeat=3):
    xyz_ = map(lambda l: l[0]*p[0] + l[1]*p[1] + l[2]*p[2], xyz)
    xyz_ = sorted(xyz_, reverse=True)
    ans = max(ans, sum(xyz_[:m]))
print(ans)
### BUGGY CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

s = 0
for i in range(N-1):
  for j in range(i+1, N):
    s += (A[i] ^ A[j])%(10**9+7)
print(s%(10**9+7))


### FIXED CODE ###

def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
A = ints()

w = 1000000007

s = 0
for k in range(60):
  n = [0, 0]
  for i in range(N):
    n[A[i]%2] += 1
    A[i] >>= 1

  s += (n[0]*n[1] << k) % w

print(s%w)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#dij
seen = [[False] * W for _ in range(H)]
h = []
# count_of_magic,x,y
heapq.heappush(h, (0,Ch,Cw))
while h:
  c,x,y = heapq.heappop(h)
  if seen[x][y]:
    continue
  seen[x][y] = True
  #print(c,x,y)
  if x == Dh and y == Dw:
    print(c)
    exit(0)
  for dx,dy in dpat:
    nx,ny = x+dx, y+dy
    if 0<=nx<H and 0<=ny<W:
      if seen[nx][ny] or S[nx][ny] == "#":
        continue
      heapq.heappush(h, (c,nx,ny))
  for dx,dy in mpat:
    nx,ny = x+dx, y+dy
    if 0<=nx<H and 0<=ny<W:
      if seen[nx][ny] or S[nx][ny] == "#":
        continue
      heapq.heappush(h, (c+1,nx,ny))
      
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
#import heapq
from collections import deque

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#BFS
visited = [[False] * W for _ in range(H)]
willSearch = [[False] * W for _ in range(H)]
Q = deque()
QN = deque()
Q.append((0,Ch,Cw))
QN.append((0,Ch,Cw))
while Q:
  while Q:
    c,x,y = Q.popleft()
    if visited[x][y]:
      continue
    visited[x][y] = True
    QN.append((c,x,y))
    #print(c,x,y)
    if x == Dh and y == Dw:
      print(c)
      exit(0)
    for dx,dy in dpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c,nx,ny))
        QN.append((c,nx,ny))
        willSearch[nx][ny] = True
  while QN:
    c,x,y = QN.popleft()
    for dx,dy in mpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c+1,nx,ny))
        #print("m", c+1, nx,ny)
        #willSearch[nx][ny] = True
      
print(-1)
### BUGGY CODE ###

T = input()
s=''
for i,c in enumerate(T):
  if c=='?':
    s+='D'
  else:
    s+=c
print(s)

### FIXED CODE ###

T = input()
print(T.replace('?','D'))
### BUGGY CODE ###


n = int(input())
s=input()

ans = 0
for i in range(1, n):
    l = s[:i]
    r = s[i:]
    if i < n/2:
        for j in range(len(l)):
            for k in range(j+ans, len(l)+1):
                if l[j:k] in r:
                    ans = k - j
    else:
        for j in range(len(r)):
            for k in range(j+ans, len(r)+1):
                if r[j:k] in l:
                    ans = k - j
print(ans)
        

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   for idx, j in enumerate(z_algo(s[i:])):
      ans = max(min(idx, j), ans)

print(ans)