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

s = input()
K = int(input())

alp = "abcdefghijklmnopqrstuvwxyz"

target = K
candidate = set()
for a in alp:
    idx_list = []
    for i, _s in enumerate(s):
        if a == _s:
            idx_list.append(i)
            candidate.add(_s)

    if len(candidate) >= K:
        break

    ng_idx_list = []
    for j in range(1, len(s) + 1):
        if set(ng_idx_list) == set(idx_list):
            break
        for _idx in idx_list:
            if _idx in ng_idx_list:
                continue
            if _idx + j > len(s) - 1:
                ng_idx_list.append(_idx)
                continue
            _sub = s[_idx: _idx + 1 + j]
            candidate.add(_sub)

    if len(candidate) >= K:
        break

print(sorted(list(candidate))[K - 1])

### FIXED CODE ###

s = input()
K = int(input())
alp = "abcdefghijklmnopqrstuvwxyz"
candidate_orig = set()

def hoge(c_list, rank, candidate):
    if len(candidate) >= 5:
        return candidate

    cur_targets = {}
    for l in sorted(c_list):
        if l + rank > len(s) - 1:
            continue
        _sub = s[l: l + 1 + rank]
        if _sub not in cur_targets:
            cur_targets[_sub] = [l]
        else:
            cur_targets[_sub].append(l)

    if len(cur_targets) == 0:
        return candidate

    for _d in sorted(cur_targets.items(), key=lambda x: x[0]):
        candidate.add(_d[0])
        candidate = hoge(_d[1], rank + 1, candidate)
        return candidate

    return candidate

for a in alp:
    idx_list = []
    for i, _s in enumerate(s):
        if a == _s:
            idx_list.append(i)
            candidate_orig.add(_s)
    candidate = hoge(idx_list, 1, candidate_orig)
    if len(candidate) >= 5:
        break

print(sorted(list(candidate_orig))[K - 1])
### BUGGY CODE ###

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for i, s in enumerate(S[::-1], start=1):
    if s == -1:
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        m = mod13_list[(s * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

from collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
# print("pointed", list([un_hash(key), val] for key, val in pointed.items()))
# print("pointing", list([un_hash(key), val] for key, val in pointing.items()))
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in START]
    dist = 1
    while Q:
        q, d = Q.pop()
        for nex in from_to[q]:
            Q.append([nex, d+1])
            dist = d+1
    print(dist)


### FIXED CODE ###

from collections import deque

n = int(input())
matches = []
for _ in range(n):
    matches.append(list(map(lambda x: int(x)-1, input().split())))

q = deque(range(n))

days = [0]*n  # 各選手の現在の日付
pairs = [-1]*n  # 次の対戦相手を管理(wait的な)

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)
### BUGGY CODE ###

s = input() # 文字列を変数に格納
t = input() # 文字列を変数に格納

p = 0
count = 0

for i in range(len(t)):
    flag = 0
    for j in range(p,len(s)):
        if t[i] == s[j]:
            p = j+1
            flag = 1
            break
    if flag == 0:
        count += 1
        for j in range(0,p):
            if t[i] == s[j]:
                p = j+1
                flag = 1
                break
    if flag == 0:
        flag = 2
        break
        
if flag == 2:
    print(-1)
else:
    print(count*len(s) + p)


### FIXED CODE ###

s = input()
t = input()

p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    if dic[ord(t[i])-97][p] == len(s)-1:
        roop += 1        
        p = 0
    else:
        p = dic[ord(t[i])-97][p] + 1

if dis == 2:
    print(-1)
else:
    print(roop*len(s)+p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)
def dfs_par(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs_par(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs_par(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(int(N / R) + 1):
    for g in range(int(N / G) + 1) :
        b = (N - r * R - g * G) / B
        if b >= 0 and b.is_integer() :
            ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(0, N + 1, R):
    if r > N :
        break
    for g in range(r, N + 1, G) :
        if g > N :
            break
        b = (N - g) / B
        if b >= 0 and b.is_integer() :
            ans += 1
print(ans)
### BUGGY CODE ###

# わからんだろこれ 降順ソート*昇順ソートからの発想が浮かばず
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
l, r = -1, 10**12 + 1  # ちゃんと「取りうることがないもののうち最大値」「取りうることのない最小値」でやる.....

while r - l > 1:
    mid = (r + l) // 2  # 最大値これをめざす
    cur = 0
    for i in range(n):
        if a[i] * b[i] <= mid:
            # Kを使う必要がない
            pass
        else:
            # Kからどんくらい使うか これむずくない？
            cur += a[i] - mid // b[i]
        if cur > k:
            l = mid
            break
        # cur += max(0, a[i] - mid // b[i])
        # if cur > k:
        #     break
    if cur > k:
        l = mid
    else:
        r = mid
print(r)

### FIXED CODE ###

# わからんだろこれ 降順ソート*昇順ソートからの発想が浮かばず
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())), reverse=True)
l, r = -1, 10**12 + 1  # ちゃんと「取りうることがないもののうち最大値」「取りうることのない最小値」でやる.....

while r - l > 1:
    mid = (r + l) // 2  # 最大値これをめざす
    cur = 0
    for i in range(n):
        if a[i] * b[i] <= mid:
            # Kを使う必要がない
            pass
        else:
            # Kからどんくらい使うか これむずくない？
            cur += a[i] - mid // b[i]
        if cur > k:
            l = mid
            break
        # cur += max(0, a[i] - mid // b[i])
        # if cur > k:
        #     break
    if cur > k:
        l = mid
    else:
        r = mid
print(r)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc143/tasks/abc143_d

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

count = 0

for i in range(N-2):
    for j in range(i + 1, N-1):
        for k in range(j + 1, N):
            if ((L_list[i] < L_list[j]+L_list[k]) 
            and (L_list[j] < L_list[k]+L_list[i]) 
            and (L_list[k] < L_list[i]+L_list[j])):
                count += 1

print(count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc143/tasks/abc143_d

import bisect

N = int(input())
L_list = list(map(int, input().split()))
L_list = sorted(L_list)
count = 0

for a in range(N-2):
    for b in range(a + 1, N-1):
        c_min = L_list[b + 1]
        c_max = L_list[a] + L_list[b]
        c_max_idx = bisect.bisect_left(L_list, c_max)
        c_count = c_max_idx - (b + 1)
        count += c_count

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

import math
N=int(input())
L=[]

for i in range(N):
  L.append(sorted(str(input())))

K=[]
C=[]

for j in range(N):
  if L[j] not in K:
    K.append(L[j])
    C.append(1)
  else:
    C[K.index(L[j])]+=1

A=0
for k in range(len(K)):
  if C[k]>1:
    if C[k]==2:
      A+=1
    else:
      A+=math.factorial(C[k])/(2*math.factorial(C[k]-2))

print(int(A))

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
d = {}
ans = 0
for string in s:
    if string in d:
        ans += d[string]
        d[string]+=1
    else:
        d[string]=1
print(ans)
### BUGGY CODE ###

n = int(input())
freq = []
slst = []
for i in range(n):
  temp = input()
  if temp not in slst:
    slst.append(temp)
    freq.append(0)
  else:
    freq[slst.index(temp)] += 1
fmax = max(freq)
mflst = []
for i in range(len(freq)):
  if freq[i] == fmax:
    mflst.append(slst[i])
mflst.sort()
for i in range(len(mflst)):
  print(mflst[i])

### FIXED CODE ###

n = int(input())
#freq = []
#slst = []
dic1 = {}
for i in range(n):
  temp = input()
  dic1.setdefault(temp, 0)
  dic1[temp] += 1
fmax = max(dic1.values())
mflst = []
ks = list(dic1.keys())
for i in dic1:
  if dic1[i] == fmax:
    mflst.append(i)
    
mflst.sort()
for i in range(len(mflst)):
  print(mflst[i])
### BUGGY CODE ###

from sys import exit

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

S = input()

AC = {}
for i in range(len(S) - 1):
    if S[i] == 'A':
        if S[i + 1] == 'C':
            AC[i] = True
            continue
    AC[i] = False

ans = []

for i in range(Q):
    li, ri = map(int, input().split())
    count = 0
    for i in range(li - 1, ri - 1):
        if AC[i]:
            count += 1
    ans.append(count)

for a in ans:
    print(a)


### FIXED CODE ###

from sys import exit

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

S = input()

AC = [0] * N

c = 0

for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        c += 1
    AC[i + 1] = c

for _ in range(Q):
    li, ri = map(int, input().split())
    print(AC[ri - 1] - AC[li - 1])
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n,k=list(map(int,input().split()))
    p = list(map(int,input().split()))

    loop=n-k+1

    ms=0

    for i in range(loop):
        tmp=0
        for j in range(k):
            tmp+=p[i+j]/2+1/2
        if tmp > ms:
            ms = tmp

    print(ms)

    return

resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n,k=list(map(int,input().split()))
    p = list(map(int,input().split()))

    loop=n-k+1

    ms=0
    bef=0
    for i in range(loop):
        tmp=0
        if i ==0:
            for j in range(k):
                tmp+=p[i+j]/2+1/2
            if tmp > ms:
                ms = tmp
        else:
            tmp=bef
            tmp-=(p[i-1]/2+1/2)
            tmp+=(p[i+k-1]/2+1/2)
            if tmp > ms:
                ms = tmp
        bef=tmp

    print(ms)

    return

resolve()
### BUGGY CODE ###

s = input()
s = s[::-1]
n = len(s)
s = '#' + s
MOD = 10**9+7
dp = [[0]*13 for _ in range(n+5)]
"""
dp[i][j] は i 桁目まで見たとき 13 で割ったあまりが j　となるようなものの個数
"""
dp[0][0] = 1
r = 1 
for i in range(1,n+1):
    for j in range(13):
        if s[i] != '?':
            dp[i][j] = dp[i-1][(j-r*int(s[i]))%13] % MOD
        if s[i] == '?':
            for k in range(10):
                dp[i][j] += dp[i-1][(j-r*k)%13]
            dp[i][j] %= MOD
    r = (r*10) % 13
print(dp[n][5])

### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
s = '#' + s
MOD = 10**9+7
dp = [[0]*13 for _ in range(n+5)]
"""
dp[i][j] は i 桁目まで見たとき 13 で割ったあまりが j　となるようなものの個数
"""
dp[0][0] = 1
r = 1 
for i in range(1,n+1):
    for j in range(13):
        if s[i] != '?':
            dp[i][j] = dp[i-1][(j-r*int(s[i]))%13] % MOD
        if s[i] == '?':
            for k in range(10):
                dp[i][j] += dp[i-1][(j-r*k)%13]
            dp[i][j] %= MOD
    r = (r*10) % 13
print(dp[n][5])
### BUGGY CODE ###


import math
x = int(input())

a = math.floor(x ** (1/5)) 

b = -1
while True:
    if a**5 -b**5 == x:
        break
    b = abs(b+1)

print(a,b)



### FIXED CODE ###

x = int(input())


for i in range(-500,500):
    for j in range(-500,500):
        if x == i**5 - j ** 5:
            print(i,j)
            exit()
### BUGGY CODE ###

#                         author:  kagemeka 
#                         created: 2019-11-07 13:42:36(JST)
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator

def main():
    s = sys.stdin.readline().rstrip()
    k = int(sys.stdin.readline().rstrip())
    n = len(s)

    substrings = []
    for i in range(1, n+1):
        for j in range(n-i+1):
            substring = s[j:j+i]
            substrings.append(substring)
            
    substrings = sorted(list(set(substrings)))
    print(substrings[k-1])


if __name__ == "__main__":
    # execute only if run as a script
    main()


### FIXED CODE ###

#                         author:  kagemeka 
#                         created: 2019-11-07 13:42:36(JST)
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator

def main():
    s = sys.stdin.readline().rstrip()
    k = int(sys.stdin.readline().rstrip())
    n = len(s)
    
    substrings = []
    for i in range(1, k+1):
        for j in range(n-i+1):
            substring = s[j:j+i]
            substrings.append(substring)
    substrings = sorted(list(set(substrings)))
    print(substrings[k-1])


if __name__ == "__main__":
    # execute only if run as a script
    main()
### BUGGY CODE ###

H, W, M = map(int, input().split())

hdic = {}
wdic = {}
hws_h = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
    else:
        wdic[w] = 1

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

for k, v in hdic.items():
    if v == hmax:
        hs.append(k)

for k, v in wdic.items():
    if v == wmax:
        ws.append(k)

f = 1
for h in hs:
    wlist = hws_h[h]
    for w in ws:
        if w not in wlist:
            f = 0
            break
    if f == 0:
        break

print(hmax + wmax - f)


### FIXED CODE ###

H, W, M = map(int, input().split())

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(ws) < len(hs):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break
        
else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    dp = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if s[-i-1] == "?":
            for j in range(10):
                if i == 0:
                    dp[0][j % 13] += 1
                else:
                    for k in range(13):
                        dp[i][(10 ** i * j + k) % 13] += (dp[i-1][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[0][int(s[-i-1]) % 13] += 1
            else:
                for k in range(13):
                    dp[i][(10 ** i * int(s[-i-1]) + k) % 13] += (dp[i-1][k] % (10 ** 9 + 7))
    print(dp[-1][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

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

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])

def bfs(pnxt):
    next_q = deque([])
    for hw in pnxt:
        next_q.append(hw)
    nxt = set([])
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)


### FIXED CODE ###

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

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)