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

from collections import deque
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = deque([(estimation_init, board_init, blank_init)])
visited = set()
while True:
    estimation, board, blank = queue.popleft()
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        queue.append((new_estimation, new_board, new_blank))


### FIXED CODE ###

from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
        
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < min(P[i:i+K-1])) and (P[i+K-1] > max(P[i:i+K-1])) and (i!=0):
        continue
    else:
        count += 1
print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
P = list(map(int,input().split()))
count = 0
first = 1
def init(init_val,n):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def segfunc(x,y):
    return max([x,y])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

def init2(init_val,n):
    #set_val
    for i in range(n):
        seg2[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg2[i]=segfunc2(seg2[2*i+1],seg2[2*i+2])

def segfunc2(x,y):
    return min([x,y])

def update2(k,x):
    k += num-1
    seg2[k] = x
    while k:
        k = (k-1)//2
        seg2[k] = segfunc2(seg2[k*2+1],seg2[k*2+2])

def query2(p,q):
    if q<=p:
        return ide_ele2
    p += num-1
    q += num-2
    res=ide_ele2
    while q-p>1:
        if p&1 == 0:
            res = segfunc2(res,seg2[p])
        if q&1 == 1:
            res = segfunc2(res,seg2[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc2(res,seg2[p])
    else:
        res = segfunc2(segfunc2(res,seg2[p]),seg2[q])
    return res

#####単位元######
ide_ele2 = 10**9

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg2=[ide_ele2]*2*num

l = [0]*(N-1)
for i in range(len(l)):
    if P[i]>=P[i+1]:
        l[i] = 1
l2 = [0]*(N-K+1)
tmp = sum(l[0:K-1])
for i in range(N-K+1):
    if tmp==0:
        l2[i]=1
    if i != N-K:
        tmp += (l[i+K-1]-l[i])
init(P,N)
init2(P,N)
for i in range(N-K+1):
    if l2[i]==1:
        if first == 1:
            count += 1
            first = 0
        continue
    elif  (P[i-1] < query2(i,i+K-1)) and (P[i+K-1] > query(i,i+K-1)) and (i!=0):
        continue
    else:
        count += 1
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
new_p = []
temp = []

for i in p:
    new_p.append(((i * (i + 1)) / 2) / i)
    
for i in range(len(p) - k + 1):
    temp.append(sum(new_p[i:i + k]))

print(max(temp))    

### FIXED CODE ###

from itertools import accumulate

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

new_p = []
temp = []
for i in p:
    new_p.append(((i * (i + 1)) / 2) / i)
q = [0] + new_p
q = list(accumulate(q))

for i in range(len(q) - k):
    temp.append(q[i + k] - q[i])
print(max(temp))
### BUGGY CODE ###

X = int(input())
ans = 0

for i in range(1, 1001):
  for j in range(2, 1001):
    num = i ** j
    if num >= ans and num <= X:
      ans = num

print(ans)

### FIXED CODE ###

X = int(input())
ans = 1

for i in range(1, X+1):
  for j in range(2, X+1):
    num = i ** j
    if num > X:
      break
    if num >= ans: 
      ans = num

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

# -*- coding: utf-8 -*-


def main():
    s = input().splitlines()[0]
    t = input()

    Slen = len(s)
    Index = -1
    Loop = 0
    LUT = [[] for i in range(26)]
    Cur = [0 for i in range(26)]

    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        LUT[v].append(i)

    for c in t:
        v = ord(c) - ord('a')
        l = len(LUT[v])
        if l == 0:
            print(-1)
            return

    for c in t:
        v = ord(c) - ord('a')
        l = len(LUT[v])
        b = -1
        for a in range(Cur[v],l):
            if LUT[v][a] > Index:
                b = a
                break
        if b < 0:
            Loop += 1
            Cur = [0 for i in range(26)]
            b = 0
        Index = LUT[v][b]

    print(Loop*Slen+Index+1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    s = input().splitlines()[0]
    t = input().splitlines()[0]

    Slen = len(s)

    LookupTable = [[] for i in range(26)]
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        LookupTable[v].append(i)
    for i in range(26):
        LookupTable[i].append(-1)
        
    IndexTable = [0 for i in range(26)]
    NextTable = []
    for i, c in enumerate(s):
        v = ord(c) - ord('a')
        NextTable.append( [LookupTable[k][IndexTable[k]] for k in range(26)] )
        IndexTable[v] += 1
        if LookupTable[v][IndexTable[v]] < 0:
            IndexTable[v] = 0

    Index = 0
    Loop = 0
    for i, c in enumerate(t):
        v = ord(c) - ord('a')
        if NextTable[Index][v] < Index:
            Loop += 1
        Index = NextTable[Index][v]
        if Index < 0:
            print(-1)
            return
        Index += 1
        if Index >= Slen:
            Index = 0
            Loop += 1

    print(Loop*Slen+Index)


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

X = int(input())

A = 0
while True:
    for B in range(A+1):
        if A ** 5 + B ** 5 == X:
            print(A, B)
            break
        if A ** 5 - B ** 5 == X:
            print(A, B)
            break
    A += 1

### FIXED CODE ###

import sys
X = int(input())

for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if i**5 - j**5 == X:
            print(i,j)
            sys.exit()
### BUGGY CODE ###

n,k = map(int,input().split())
mod = 998244353

s = []
for i in range(k):
    l,r = map(int,input().split())
    for i in range(l,r+1):
        s.append(i)
s.sort()
# print(s)
dp = [0 for i in range(n+1)]
dp[1] = 1
for i in range(2,n+1):
    for j in s:
        if i-j >= 1:
            dp[i] += dp[i-j]
    # print(dp)
print(dp[n] % mod)

### FIXED CODE ###

n,k = map(int,input().split())
mod = 998244353

l,r = [0]*k,[0]*k
for i in range(k):
    ll,rr = map(int,input().split())
    l[i],r[i] = ll,rr

dp = [0]*(n+1)
dpsum = [0]*(n+1)
dp[1], dpsum[1] = 1,1
for i in range(2,n+1):
    for j in range(k):
        li = i - r[j]
        ri = i - l[j]
        if ri < 0:
            continue
        dp[i] += dpsum[ri] - dpsum[li-1]
        dp[i] %= mod
    dpsum[i] = dpsum[i-1] + dp[i]
print(dp[n])
### BUGGY CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck *= pow(k + 1, LARGE - 2, LARGE)
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    factorial_n = 1
    factorial_inv = [0] * (n + 1)
    factorial_inv[0] = 1
    for i in range(1, n + 1):
        factorial_n *= i
        factorial_n %= LARGE
    factorial_inv[-1] = pow(factorial_n, LARGE - 2, LARGE)
    for i in range(n):
        factorial_inv[n - i - 1] = (factorial_inv[n - i] * (n - i)) % LARGE
    pow_2 = 1
    for k in range(n // 2):
        r += factorial_n * factorial_inv[n - k] * factorial_inv[k] * pow_2
        r %= LARGE
        pow_2 *= 2
        pow_2 %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


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

import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b, dtype='i8')

for i in range(1, H):
    a[i:, :] = np.minimum(a[i:, :], a[i-1:-1, :] + 1)
for i in range(H - 1, 0, -1):
    a[:i, :] = np.minimum(a[:i, :], a[1:i+1, :] + 1)
for j in range(1, W):
    a[:, j:] = np.minimum(a[:,j:], a[:, j-1:-1] + 1)
for j in range(W -1, 0, - 1):
    a[:, :j] = np.minimum(a[:, :j], a[:, 1:j+1] + 1)

print(np.max(a))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break
### BUGGY CODE ###

import math
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
csf = [IL() for i in range(N-1)]

ans = [0]*N

for j in range(N-1):
	for i in range(j,N-1):
		if ans[j] <= csf[i][1]:
			ans[j] = csf[i][1] + csf[i][0]
			continue
		else:
			tmp = csf[i][1]//csf[i][2]
			while csf[i][2]*tmp < ans[j]:
				tmp += 1
			ans[j] = csf[i][2]*tmp + csf[i][0]

for i in ans:
	print(i)

### FIXED CODE ###

import math
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
csf = [IL() for i in range(N-1)]

ans = [0]*N

for j in range(N-1):
	for i in range(j,N-1):
		if ans[j] <= csf[i][1]:
			ans[j] = csf[i][1] + csf[i][0]
			continue
		else:
			tmp = ans[j]//csf[i][2]
			while csf[i][2]*tmp < ans[j]:
				tmp += 1
			ans[j] = csf[i][2]*tmp + csf[i][0]

for i in ans:
	print(i)
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
for i in range(2, 10 ** 12 + 1):
    if C == 1:
        break
    while True:
        if C % i != 0:
            break
        ans.append(i)
        C //= i
print(len(set(ans)) + 1)


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


A, B = map(int, input().split())
C = gcd(A, B)

ans = []
while C % 2 == 0:
    ans.append(2)
    C //= 2
i = 3
while C >= i * i:
    if C % i == 0:
        ans.append(i)
        C //= i
    else:
        i += 2
if C != 1:
    ans.append(C)
print(len(set(ans)) + 1)
### BUGGY CODE ###

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    counter = 1
    while counter != n:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
        counter += 1
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
x_sort = [] #[Xi,Yi,点番号]
y_sort = [] #[Yi,Xi,点番号]
for i in range(n):
    X,Y = map(int,input().split())
    x_sort.append([X,Y,i])
    y_sort.append([Y,X,i])
x_sort.sort()
y_sort.sort()
for i in range(1,n):
    edge[x_sort[i][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i-1][2]])
    edge[x_sort[i-1][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
print(prim_heap())

### FIXED CODE ###

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
p=[]
edge=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    edge[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    edge[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    edge[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    edge[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))

print(prim_heap())
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ct=0
for i1 in range((n//r)+1):
  for i2 in range((n//g)+1):
    if (n-r*i1-g*i2)%b==0 and n-r*i1-g*i2>=0:
      ct+=1
print(ct)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ct=0
for i1 in range((n//r)+1):
  for i2 in range((n//g)+1):
    if (n-r*i1-g*i2)%b==0 and n-r*i1-g*i2>=0:
      ct+=1
print(ct)
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * (N+1) for _ in range(N+1)]

for i in range(N+1):
    d[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())

    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c


for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]][p[i+1]]

    ans = min(ans, dist)

print(ans)


### FIXED CODE ###

import itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * N for _ in range(N)]

for i in range(N):
    d[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

# for k in range(N):
#     for i in range(N):
#         for j in range(N):
#             d[i][j] = min(d[i][j], d[i][k] + d[k][j])

d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

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

from collections import deque
from collections import Counter
S = list((input()))
A = deque([0])
B = deque([])
for i in range(len(S)):
    n = int(''.join(S[len(S)-2-i:]))
    A.append(n)
for j in A:
    B.append(j%2019)
C = Counter(B)
cnt= 0
for v in C.values():
    cnt += v*(v-1)//2
print(cnt)

### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

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

ans = 0

for i in range(n):
    if p[i] <= min(p[0:i+1]):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
cnt=1
tmp=P[0]
for i in range(1, N):
    tmp = min(tmp, P[i-1])
    if tmp >= P[i]:
        cnt+=1
#         print(i, cnt)
        
print(cnt)
### BUGGY CODE ###

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

ans = 1

for i in range(0, n):
    if a[i] == 0:
        print(0)
        exit()
    ans *= a[i]

m = 10 ** 18

if ans > m:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 10**18

ans = 1

for i in range(0, n):
    if a[i] == 0:
        print(0)
        exit()

for i in range(0, n):
    ans *= a[i]
    if ans > m:
        print(-1)
        exit()


if ans > m:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = h*w
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == "#":
        white.append((i,j))
        count -= 1
        visit[i][j] = True
        
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while count > 0:
   ans += 1
   newwhite = []
   while white:
      x,y = white.pop(0)
      for dx,dy in d:
        nx,ny = x+dx,y+dy
        if nx < 0 or nx >= h or ny < 0 or ny >=w :
         continue 
        elif visit[nx][ny]:continue
          
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
          visit[nx][ny] =True
          if count == 0:
            print(ans)
            exit()
   white = newwhite
    
  print(ans)
solve()


### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
### BUGGY CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    didx = collections.defaultdict(int)
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)


    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

### FIXED CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()