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

import heapq
MAX_VALUE = 10**100
S = input()
lenS = len(S)
T = input()
Si = {}
for i,s in enumerate(S):
  if s not in Si:
    Si[s] = []
  heapq.heappush(Si[s],i)

ans = 0
for t in T:
  if t not in Si:
    print(-1)
    exit()
  else:
    idx = -1
    if ans<=max(Si[t]):
      while idx<ans:
        idx = heapq.heappop(Si[t])
        heapq.heappush(Si[t],idx+lenS)
    else:
      factor = (ans-min(Si[t]))//lenS
      idx = heapq.heappop(Si[t])
      heapq.heappush(Si[t],idx+lenS*factor)
      while idx<ans:
        idx = heapq.heappop(Si[t])
        heapq.heappush(Si[t],idx+lenS)
    ans = idx
    if MAX_VALUE<ans:
      print(-1)
      exit()
print(ans+1)

### FIXED CODE ###

import bisect

REPEAT_NUM = 10 ** 100

S = input()
T = input()
lenS = len(S)
lenT = len(T)

idxes_S = {}
for idx, s in enumerate(S):
    if s not in idxes_S:
        idxes_S[s] = []
    idxes_S[s].append(idx)

idx_s = -1
idx_t = 0
while idx_t < lenT and idx_s < lenS * REPEAT_NUM:
    if T[idx_t] not in idxes_S:
        print(-1)
        exit()
    else:
        tmp_idx = bisect.bisect(idxes_S[T[idx_t]], idx_s % lenS)
        if len(idxes_S[T[idx_t]]) == tmp_idx:
            idx_s += lenS - idx_s % lenS + idxes_S[T[idx_t]][0]
        else:
            idx_s += idxes_S[T[idx_t]][tmp_idx] - idx_s % lenS
        idx_t += 1

if idx_t == lenT:
    print(idx_s + 1)
else:
    print(-1)
### BUGGY CODE ###

n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)

for _ in range(m):
    u,v = map(int,input().split())
    dic[u-1].append(v-1)

G = defaultdict(list)
def dfs(p, s, l):
    if l == 3:
        if s != p:
            G[s].append(p)
    else:
        for i in dic[p]:
            dfs(i, s, l+1)

for i in range(n):
    dfs(i, i, 0)
s,t = map(int,input().split())

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*n
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print(dist[t-1])

### FIXED CODE ###

import sys

input = sys.stdin.readline
n,m = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)

for _ in range(m):
    u,v = map(int,input().split())
    dic[u-1].append(v-1+n)
    dic[u - 1+n].append(v - 1 + 2*n)
    dic[u - 1+2*n].append(v - 1)

G = dic
s,t = map(int,input().split())

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*(n*3)
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print(dist[t-1]//3)
### BUGGY CODE ###

def main(): 
    """
    カレンダーらしいもの: 7列…
    """
    n, k = map(int, input().split())

    part1(n, k)


def part1(n, k):
    ans = 0

    for i in range(1, n-3+2):
        for j in range(1, 5+1):
            s = 0
            for y in range(3):
                for x in range(3):
                    s += 7*(i+y) + (j+x) - 7
            # print(i, j, s, sep="\t")
            if s % 11 == k:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """
    カレンダーらしいもの: 7列…

    3x3の和: 2列目x3
    2列目の平均: (2,2)
    より,(2,2)*9

    11で割った余り
    9............13
    16...........20
    ...

    9,10,0,1,2
    5,6, 7,8,9

    [以下、解説の(自分用の)補完]
    9x ≡  k mod 11
     x ≡ 5k mod 11 ?

    わからんーとTweetしたら, 引用で解説されてた(感謝)
    1. https://twitter.com/hogeover30/status/995618880830636032
    2. https://mathtrain.jp/mod

        45x     ≡ 5k mod 11 (両辺等倍しても剰余は変わらない, 性質3)
        44x + x ≡ 5k mod 11 (求めたいxと 11で割り切れる倍数に分解, 性質1)
              x ≡ 5k mod 11

    範囲の変更
        7i + j - 7 (2<=i<=n-1, 2<=j<=6)
        7i + j + 9 (0<=i<=n-3, 0<=j<=4)
            7*2 + 1*2 = 16
            16 - 7 = 9

    7i に着目(入力例4, n=100, k=8)
        j=0: 7i+9  ≡ 5k ≡ 40 (mod 11) => 7i ≡ 9 (mod 11) ※1
        j=1: 7i+10 ≡ 5k ≡ 40 (mod 11) => 7i ≡ 8 (mod 11) ※2
            ※1: 40-9 (31) mod 11 = 9 より (性質2)
            ※2: 40-10(30) mod 11 = 8 より

            i={6,17,28,39,50,61,72,83,94}
            i={9,20,31,42,53,64,75,86,97}

    j固定: i = 11q + r
        1: r=6
        2: r=9
    結局、規則はなんとなく分かるが証明しろと言われると説明できない
    """
    n, k = map(int, input().split())

    # part1(n, k)
    # f2(n, k)
    editorial(n, k)


def f2(n, k):
    """規則をなんとなく見つけた場合
    """
    table = []
    for i in range(2, 2+11):
        table.append(
            [(7*i + j - 7) * 9 % 11 for j in range(2, 6+1)]
        )

    # 最初と最後の1行ずつ不要
    n -= 2
    # 11ごとに1つ解が存在し5列分
    ans = n // 11 * 5
    # 余った行ごとに残りの判定
    x = n % 11
    for i in range(x):
        for j in range(5):
            if table[i][j] == k:
                ans += 1

    print(ans)


def editorial(n, k):
    ans = 0
    # 列ごと: 2行目2-6列目
    for j in range(2, 6+1):
        rownum = 0
        for i in range(2, n):
            s = (i * 7 + j - 7) * 9
            if s % 11 == k:
                rownum = i
                break

        if rownum == 0:
            continue

        # 11行ごとに余りkになるため、見つかった基準の分の+1
        # 最後の1行不要, rownumずらしておく
        ans += 1
        ans += (n - 1 - rownum) // 11

    print(ans)


def part1(n, k):
    ans = 0

    for i in range(1, n-3+2):
        for j in range(1, 5+1):
            s = 0
            for y in range(3):
                for x in range(3):
                    s += 7*(i+y) + (j+x) - 7
            # print(i, j, s, sep="\t")
            if s % 11 == k:
                ans += 1

    print(ans)


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

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

ans = 0
a = A.index(max(A))
for i in range(1,N):
    if a < i:
        ans += max(A)-A[i]
    elif A[i-1] > A[i]:
        ans += A[i-1]-A[i]

print(ans)

### FIXED CODE ###

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

ans = 0
high = 0
for i in range(1,N):
    af = A[i]
    bf = A[i-1]
    if bf > high:
        high = bf
    if high > af:
        ans += high - af

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

#21 D - Banned K
import collections
N = int(input())
A = list(map(int,input().split()))

cnt = collections.Counter(A)

ans = []
for i in A:
    cnt_cpy = cnt.copy()
    cnt_cpy[i] -= 1
    comb = 0
    for j in cnt_cpy.values():
        if j >= 2:
            comb += (j*(j-1))//2
    ans.append(comb)
for k in ans:
    print(k)

### FIXED CODE ###

#21 D - Banned K AC TLE(hint)
import collections
N = int(input())
A = list(map(int,input().split()))

cnt = collections.Counter(A)
#先に組み合わせの個数を計算しておく
combinations = {}
for j in cnt.keys():
    if cnt[j] >= 2:
        comb = (cnt[j]*(cnt[j]-1))//2
        combinations[j] = comb      

#あるボールを選ばないとき、組み合わせの総数は
#(全組み合わせ数) - (選ばないボールと同じボールの数 - 1)
tot = sum(combinations.values())
ans = []
for i in A:
    a = tot - (cnt[i] - 1)
    ans.append(a)
    
for k in ans:
    print(k)
### BUGGY CODE ###

delta = ((1, 0), (0, 1), (-1, 0), (0, -1))
def ds(here, field, count, lb, ub):
	if count == 11:
		return count
	ans = 11
	for dx, dy in delta:
		neighbor = (here[0]+dx,here[1]+dy)
		nx, ny = neighbor
		tmp = 11
		while lb[0] <= nx <= ub[0] and lb[1] <= ny <= ub[1]:
			if field[ny][nx] == 1:
				if not(nx == neighbor[0] and ny == neighbor[1]):
					field[ny][nx] = 0
					tmp = ds((nx-dx,ny-dy),field, count+1, lb, ub)
		    		field[ny][nx] = 1
				break
			if field[ny][nx] == 3:
				tmp = count + 1
				break
			nx += dx
			ny += dy
		if tmp < ans:
			ans = tmp 
	return ans
while 1:
	w, h = map(int,raw_input().split(" "))
	if w == h == 0: break
	board = [ map(int,raw_input().split(" ")) for _ in range(h)]
	for j in range(h):
		for i in range(w):
			if board[j][i] == 2:
				start = (i,j)
	ans = ds(start, board, 0, (0,0), (w-1,h-1)) 
	print ans if ans < 11 else -1

### FIXED CODE ###

delta = ((1, 0), (0, 1), (-1, 0), (0, -1))
def ds(here, field, count, lb, ub, min_count):
	if count == min_count:
		return min_count
	ans = min_count
	for dx, dy in delta:
		nx, ny = (here[0]+dx,here[1]+dy)
		neighbor = (nx, ny)
		while lb[0] <= nx <= ub[0] and lb[1] <= ny <= ub[1]:
			if field[ny][nx] == 1:
				if (nx, ny) != neighbor:
					field[ny][nx] = 0
					ans = ds((nx-dx,ny-dy),field, count+1, lb, ub, ans)
		    		field[ny][nx] = 1
				break
			if field[ny][nx] == 3:
				if count + 1 < ans:
					ans = count + 1
				break
			nx += dx
			ny += dy
	return ans
while 1:
	w, h = map(int,raw_input().split(" "))
	if w == h == 0: break
	board = [ map(int,raw_input().split(" ")) for _ in range(h)]
	for j in range(h):
		for i in range(w):
			if board[j][i] == 2:
				start = (i,j)
	result = ds(start, board, 0, (0,0), (w-1,h-1), 11)
	print result if result < 11 else -1
### BUGGY CODE ###

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

from collections import Counter
C = Counter(A)

X = [0]*(10**6+1)
A.sort()
ans = 0
for a in A:
    if X[a] == 0 and C[a] == 1:
        ans += 1
    X[a] += 1
    j = 2*a
    while j <= 10**6:
        X[j] += 1
        j += a
print(ans)


### FIXED CODE ###

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

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

    #divisors.sort(reverse=True)
    return divisors

def main():
    A.sort()
    S = set(A)
    m = max(A)
    X = [0]*(m+1)
    for i in range(1, m+1):
        j = i
        if j not in S:
            continue
        while j <= m:
            X[j] += 1
            j += i
    #print(X)

    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1

    ans = 0
    for a in A:
        if X[a] == 1 and D[a] == 1:
            ans += 1
    print(ans)

    #for i in range(m+1):
    #    if X[i] == 1:
            #print(i)

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

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 3*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

ans = 0
for i in range(X,K+X+1):
    temp = 1
    A = i-X
    B = K+X-i
    temp *= cmb(A+X-1,X-1,mod)*power(25,A,mod)
    temp %= mod
    temp *= power(26,B,mod)
    ans += temp
    ans %= mod
print(ans)

### FIXED CODE ###

K = int(input())
S = input()
X = len(S)
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


A = 0
B = K
temp = cmb(A+X-1,X-1,mod)*power(25,A,mod)
temp %= mod
temp *= power(26,B,mod)
temp %= mod

ans = temp

for i in range(X+1,K+X+1):

    temp *= 25
    temp %= mod
    
    temp *= pow(26, mod-2, mod)
    temp %= mod
    
    temp *= i-1
    temp %= mod
    
    temp *= pow(i-X, mod-2, mod)
    temp %= mod    

    ans += temp
    ans %= mod

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

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n: d[o].add(s[i])
    if i<m: d[p].add(t[i])
    if i<n and len(d[o])==2: f=-1
    if i<m and len(d[p])==2: f=-1
print(f)

### FIXED CODE ###

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d={}
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n and o not in d:
        d[o]=s[i]
    elif i<n and o in d and d[o]!=s[i]:
        f=-1
    if i<m and p not in d:
        d[p]=t[i]
    elif i<m and p in d and d[p]!=t[i]:
        f=-1
print(f)
### BUGGY CODE ###

import numpy
n, m = map(int, input().split())
a = numpy.array([0] + list(map(int, input().split())), dtype=numpy.float64)

acs = numpy.cumsum(a)
cnt = 0

for l in range(n):
    for r in range(l, n):
        if (acs[r] - acs[l - 1]) % m == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
table = {0: 0}
buf = 0
cnt = 0
for i in range(n):
    buf = (buf + a[i]) % m
    if buf in table:
        cnt += table[buf]
        table[buf] += 1
    else:
        table[buf] = 1
print(cnt + table[0])
### BUGGY CODE ###

N_W=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
knapsack=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
	for w in range(1,W+1):
		if w-items[i][0]>=0:
			knapsack[i+1][w]=max(knapsack[i+1][w],knapsack[i][w],knapsack[i][w-items[i][0]]+items[i][1])
		else:
			knapsack[i+1][w]=max(knapsack[i+1][w],knapsack[i][w])
print(knapsack[-1][-1])

### FIXED CODE ###

N_W=list(map(int,input().split()))
N=N_W[0]
W=N_W[1]
items=[]
for i in range(N):
	sets=list(map(int,input().split()))
	items.append(sets)
knapsack=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
	for w in range(1,W+1):
		if w-items[i][0]>=0:
			knapsack[i+1][w]=max(knapsack[i+1][w],knapsack[i][w],knapsack[i][w-items[i][0]]+items[i][1])
		else:
			knapsack[i+1][w]=max(knapsack[i+1][w],knapsack[i][w])
print(knapsack[-1][-1])
### BUGGY CODE ###

#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
from functools import lru_cache
import numpy as np

input = stdin.readline
setrecursionlimit(1000)

#constant
H, W = list(map(int,input().split()))
S = [input() for _ in range(H)]

#variable

#function
#@lru_cache(maxsize=None)

#class

#main function
def main():
    L = np.zeros((H,W))
    R = np.zeros((H,W))
    U = np.zeros((H,W))
    D = np.zeros((H,W))

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i,j] = 0
            elif S[i][j] == ".":
                if j == 0:
                    L[i,j] = 1
                else:
                    L[i,j] = L[i,j-1] + 1

            if S[i][W-j-1] == "#":
                R[i,W-j-1] = 0
            elif S[i][W-j-1] == ".":
                if j == 0:
                    R[i,W-j-1] = 1
                else:
                    R[i,W-j-1] = R[i,W-j] + 1

            if S[i][j] == "#":
                U[i,j] = 0
            elif S[i][j] == ".":
                if i == 0:
                    U[i,j] = 1
                else:
                    U[i,j] = U[i-1,j] + 1

            if S[H-i-1][j] == "#":
                D[H-i-1,j] = 0
            elif S[H-i-1][j] == ".":
                if i == 0:
                    D[H-i-1,j] = 1
                else:
                    D[H-i-1,j] = D[H-i,j] + 1

    maxScore = 0
    score = np.array([L[i,j]+R[i,j]+U[i,j]+D[i,j]-3 for i in range(H) for j in range(W)])
    #for i in range(H):
    #    for j in range(W):
    #        score = L[i,j]+R[i,j]+U[i,j]+D[i,j]-3
    #        if score > maxScore:
    #            maxScore = score
    print(int(score.max()))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129D-Lamp.py

#import list
import sys
import numpy as np

#main function
def main():
    buffer = sys.stdin.buffer
    H, W = list(map(int,buffer.readline().split()))
    S = np.frombuffer(buffer.read(H*(W+1)), dtype="B") == ord(".")
    S = S.reshape((H,W+1))[:,:-1]
    L = np.empty((H,W), dtype="i4")
    R = np.empty((H,W), dtype="i4")
    U = np.empty((H,W), dtype="i4")
    D = np.empty((H,W), dtype="i4")

    L[:,0] = S[:,0]
    for i in range(1,W):
        L[:,i] = (L[:,i-1] + 1) * S[:,i]

    R[:,-1] = S[:,-1]
    for i in range(1,W):
        R[:,-1-i] = (R[:,-i] + 1) * S[:,-1-i]

    U[0] = S[0]
    for i in range(1,H):
        U[i] = (U[i-1] + 1) * S[i]

    D[-1] = S[-1]
    for i in range(1,H):
        D[-1-i] = (D[-i] + 1) * S[-1-i]

    score = L + R + U + D - 3
    print(int(score.max()))


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

N = int(input())

def f9(a,i):
    if a < 9**i:
        return i-1
    return f9(a,i+1)

def f6(a,i):
    if a < 6**i:
        return i-1
    return f6(a,i+1)

def func(a,ans):
    if a < 6:
        return ans+a
    elif a < 9:
        return ans+1+(a-6)
    return min(func(a-6**f6(a,0),ans+1),func(a-9**f9(a,0),ans+1))

print(func(N,0))

### FIXED CODE ###

N = int(input())

def f9(a,i):
    if a < 9**i:
        return i-1
    return f9(a,i+1)

def f6(a,i):
    if a < 6**i:
        return i-1
    return f6(a,i+1)

def func(a,ans):
    if a < 6:
        return ans+a
    elif a < 9:
        return ans+1+(a-6)
    return min(func(a-6**f6(a,0),ans+1),func(a-9**f9(a,0),ans+1))

print(func(N,0))
### BUGGY CODE ###

#125
import fractions
n = int(input())
a = [int(x) for x in input().split(' ')]
all_m = []
for i in range(1,n-1):
    a_1 = a[:i]
    a_2 = a[i+1:]
    m_1 = a_1[0]
    m_2 = a_2[0]
    for j in range(len(a_1)-1):
        m_1 = fractions.gcd(m_1,a_1[j+1])
    for j in range(len(a_2)-1):
        m_2 = fractions.gcd(m_2,a_2[j+1])
    all_m.append(fractions.gcd(m_1,m_2))
m = a[1]
for j in range(1,n-1):
    m = fractions.gcd(m,a[j+1])
all_m.append(m)
m = a[0]
for j in range(n-2):
    m = fractions.gcd(m,a[j+1])
all_m.append(m)
print(max(all_m))

### FIXED CODE ###

#125
from fractions import gcd
n = int(input())
a = [int(x) for x in input().split(' ')]

m_r = [0]
for i in range(n-1):
    m_r.append(gcd(m_r[-1], a[i]))

m_l = [0]
for i in range(1, n):
    m_l.append(gcd(m_l[-1], a[-i]))

m = []
for i in range(n):
    m.append(gcd(m_r[i], m_l[-i-1]))
print(max(m))
### BUGGY CODE ###

import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
INF=1000000000
cnt = [[INF]*(w+4) for i in range(h+4)]
ch+=1; cw+=1; dh+=1; dw+=1

def bfs7():
    '''
    collections.dequeを使う
    mを書き換えない ,cntを使う
    '''
    Q=deque()
    cnt[ch][cw]=0
    Q.append((ch,cw))

    while Q:
        i,j=Q.popleft() 
        for si,sj in ad:
            if m[i+si][j+sj]=='.' and cnt[i][j]<cnt[i+si][j+sj]:# and cnt[i+si][j+sj]==-1はいらないはず
                cnt[i+si][j+sj]=cnt[i][j]
                Q.appendleft((i+si,j+sj))

        for si,sj in warp:
            if m[i+si][j+sj]=='.' and cnt[i][j]+1<cnt[i+si][j+sj]:
                cnt[i+si][j+sj]=cnt[i][j]+1
                Q.append((i+si, j+sj))
                
bfs7()

if cnt[dh][dw] == INF:
    print(-1)
else:
    print(cnt[dh][dw])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

ch-=1; cw-=1; dh-=1; dw-=1

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
ch+=2; cw+=2; dh+=2; dw+=2

def bfs4():
    '''
    bfs3とほぼ同じ. 迷路の上下左右に2列ずつ壁追加
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex

        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            # 隣接したマスへの移動
            for si, sj in ad:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1

        # 歩いていけないマス
        for i,j in que1:
            for si, sj in warp:
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))

        que1=que2
        que2=[]
###---------------------------------------

bfs4()


if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])
### BUGGY CODE ###

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    if a[m] >= k:
        r = m
        continue
    dp = [set() for _ in range(n + 1)]
    dp[0].add(0)
    check = 0
    for i in range(n):
        if i == m:
            dp[i + 1] = dp[i]
            continue
        for x in dp[i]:
            dp[i + 1].add(x)
            temp = x + a[i]
            if k - a[m] <= temp < k:
                check = 1
                break
            elif temp < k - a[m]:
                dp[i + 1].add(temp)
        if check == 1:
            break
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

### FIXED CODE ###

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

a.sort(reverse=True)

temp = 0
ans = 0

for x in a:
    if temp + x < k:
        temp += x
        ans += 1
    else:
        ans = 0

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

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
S = list(input())
ans = []
for i in range(N+1):
    ans.append(S[0:i].count('W') + S[i + 1:N + 1].count('E'))
print(str(min(ans)))


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
S = input()
ans = S[1:N].count('E')
tmp = ans
for i in range(N-1):
    if S[i] == 'W':
        tmp += 1
    if S[i + 1] == 'E':
        tmp -= 1
    ans = min(tmp, ans)
print(str(ans))
### BUGGY CODE ###

n=int(input())
c=[''.join(sorted(input())) for _ in range(n)]
an=0

for i in set(c):
    t=c.count(i)
    for j in range(t):
        an+=j

print(an)

### FIXED CODE ###

n=int(input())
c=[''.join(sorted(input())) for _ in range(n)]
an=0
d={}

for i in c:
    if i in d:
        an += d[i]
        d[i]+=1
    else:
        d[i]=1

print(an)