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

from math import factorial
S=list(map(int,input()))
S.reverse()
# print(S)
count2019 = [0]*2019
count2019[0]=1
mod2019 = [0]*(len(S)+1)
for i in range(len(S)):
    mod2019[i+1] =mod2019[i]+S[i]*10**i 
    mod2019[i+1]%=2019
    count2019[mod2019[i+1]] +=1

ans =0
for i in count2019:
    if(i>=2):
        ans += factorial(i) // factorial(i) // factorial(i - 2)
print(ans)
# print(count2019)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    INF =  float('inf')
    dp = [INF for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,k+1):
            if i+j<n:
                dp[i+j] = min(dp[i]+abs(h[i]-h[i+j]),dp[i+j])
            else:
                break
                
    print(dp[n-1])

main()

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    INF =  float('inf')
    dp = [INF for i in range(n)]
    dp[0] = 0
    dp[1] = abs(h[0]-h[1])
    for i in range(2,n):
        dp[i] = min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,min(i,k)+1))
    print(dp[n-1])

main()
### BUGGY CODE ###

N ,K = map(int,input().split())
P = list(map(int,input().split()))
ex = []
ans = 0
for i in range(N-K+1):
    ans = (sum(P[i:i+K])+K)/2
    ex.append(ans)
    ans = 0
print(max(ex))

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
for i in range(N):
  P[i]=(P[i]+1)/2
point=sum(P[:K])
tmp=point
for i in range(N-K):
  tmp=tmp-P[i]+P[i+K]
  if tmp>point:point=tmp
  
print(point)
### BUGGY CODE ###

n=int(input())
s=[input()for _ in range(n)]
def check(s,t):
  for i in range(n):
    for j in range(n):
      if s[(i+t)%n][j]!=s[(j+t)%n][i]:return False
  return True
ans=0
for i in range(n):
  if check(s,i):ans+=n
print(ans)

### FIXED CODE ###

n=int(input())
s=[input()for _ in range(n)]
def check(s,t):
  for i in range(n):
    for j in range(n):
      if s[(i+t)%n][j]!=s[(j+t)%n][i]:return False
  return True
ans=0
for i in range(n):
  if check(s,i):ans+=n
print(ans)
### BUGGY CODE ###

N=int(input())

def func(x,y,z):
  return x*x+y*y+z*z+x*y+y*z+z*x

for i in range(1,N+1):
  answer_set=set()
  for x in range(int(i**0.5)+1):
    for y in range(1,x+1):
      if func(x,y,1)>i:
        break
      for z in range(1,y+1):
        if func(x,y,z)==i:
          answer_set.add((x,y,z))
          answer_set.add((x,z,y))
          answer_set.add((y,x,z))
          answer_set.add((y,z,x))
          answer_set.add((z,y,x))
          answer_set.add((z,x,y))
        elif func(x,y,z)>i:
          break
          
  print(len(answer_set))

### FIXED CODE ###

N=int(input())

def func(x,y,z):
  return x*x+y*y+z*z+x*y+y*z+z*x

for i in range(1,N+1):
  answer_set=set()
  for x in range(int(i**0.5)+1):
    for y in range(1,x+1):      
      for z in range(1,y+1):
        if func(x,y,z)==i:
          answer_set.add((x,y,z))
          answer_set.add((x,z,y))
          answer_set.add((y,x,z))
          answer_set.add((y,z,x))
          answer_set.add((z,y,x))
          answer_set.add((z,x,y))
        elif func(x,y,z)>i:
          break
          
  print(len(answer_set))
### BUGGY CODE ###

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

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and black[nh][nw+1] == 0:
        qq.append([nh,nw+1])
        black[nh][nw+1] = black[nh][nw]+1
      if  0<=nw-1 and black[nh][nw-1] == 0:
        qq.append([nh,nw-1])
        black[nh][nw-1] = black[nh][nw]+1
      if nh+1<=H-1 and black[nh+1][nw] == 0:
        qq.append([nh+1,nw])
        black[nh+1][nw] = black[nh][nw]+1
      if 0<=nh-1 and black[nh-1][nw] == 0:
        qq.append([nh-1,nw])
        black[nh-1][nw] = black[nh][nw]+1
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math
import collections
import sys

h, w, m = map(int, input().split())
x = []
y = []
bomb = []
for i in range(m):
  tmp_x, tmp_y = map(int, input().split())
  x.append(tmp_x)
  y.append(tmp_y)
  bomb.append([tmp_x, tmp_y])

c_x = collections.Counter(x)
c_y = collections.Counter(y)
_max_x = c_x.most_common()[0][1]
_max_y = c_y.most_common()[0][1]
ys = c_y.most_common()
count = _max_x + _max_y - 1
      
tansaku_x = []
tansaku_y = []
for x, x_num in c_x.most_common():
  if x_num != _max_x:
    break
  tansaku_x.append(x)
for y, y_num in c_y.most_common():
  if y_num != _max_y:
    break
  tansaku_y.append(y)

for x in tansaku_x:
  for y in tansaku_y:
    if [x, y] in bomb:
      continue
    else:
      print(count+1)
      sys.exit()
      
print(count)

### FIXED CODE ###

h,w,n=map(int,input().split())
H=[0]*h
W=[0]*w
L=[(0,0)]*n
for i in range(n):
    a,b=map(int,input().split())
    L[i]=(a,b)
    H[a-1]+=1
    W[b-1]+=1
h_max=max(H)
w_max=max(W)
ans=h_max+w_max
cnt=0
for l in L:
    if H[l[0]-1]==h_max and W[l[1]-1]==w_max:
        cnt+=1
if H.count(h_max)*W.count(w_max)==cnt:
    ans-=1
print(ans)
### BUGGY CODE ###

import math
from fractions import Fraction

x = int(input())
rad = Fraction((math.pi / 180) * x)

k = 0
while True:
    k += 1
    s = rad * k
    if s % (math.pi * 2) == 0:
        break
print(k)

### FIXED CODE ###

import math
from fractions import Fraction

x = int(input())


k = 0
while True:
    k += 1
    s = x * k
    if s % 360 == 0:
        break
print(k)
### BUGGY CODE ###

a,b,m=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
tickets=list()
for i in range(m):
    tickets.append(list(map(int,input().split())))

price_min=float("INF")
for ticket in tickets:
    price = A[ticket[0]-1] + B[ticket[1]-1] - ticket[2]
    price_min = price if price_min>price else price_min

# 割引券を使わない場合
for _a in A:
    for _b in B:
        price=_a + _b
        price_min=price if price_min > price else price_min
        if price <_a:
            break
print(price_min)

### FIXED CODE ###

a,b,m=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
tickets=list()
for i in range(m):
    tickets.append(list(map(int,input().split())))

price_min=float("INF")
for ticket in tickets:
    price = A[ticket[0]-1] + B[ticket[1]-1] - ticket[2]
    price_min = price if price_min>price else price_min

# 割引券を使わない場合
no_ticket=min(A)+min(B)
if price_min > no_ticket: price_min=no_ticket
print(price_min)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for a in range(k+1):
    for b in range(k+1):
        if a + b > s:
            break
        for c in range(k+1):
            if a + b + c == s:
                ans += 1
            elif a + b + c > s:
                break
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for a in range(k+1):
    for b in range(k+1):
        if 0 <= s - a - b <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for _ in range(m):
    b, c= map(int, input().split())
    if a[n-1] < c:
        for i in range(b):
            a.append(c)
        a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = sorted(list(map(int, readline().split())))
bc = [tuple(map(int, readline().split())) for i in range(m)]
bc.sort(key=lambda x: x[1], reverse=True)
index = 0
cnt = 0
for i in range(n):
    if a[i] > bc[index][1]:
        break
    a[i] = bc[index][1]
    cnt += 1
    if cnt == bc[index][0]:
        cnt = 0
        index += 1
        if index == m:
            break
print(sum(a))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
max_len = len(format(max(a), "b"))
a = [format(a[i], "b") for i in range(n)]
b = [0 for _ in range(max_len)]

for i in range(n):
    for j in range(1, 1+len(a[i])):
        if int(a[i][-j]):
            b[j-1] += 1

result = 0
for i in range(max_len):
    r = b[i]*(n-b[i])
    for j in range(i):
        r = r*2 %mod
    result += r
print(result%mod) 

### FIXED CODE ###

import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())
x_max=0
for x in range(N+1):
    x_max=max(math.floor(A*x/B)-A*math.floor(x/B),x_max)
print(x_max)

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
def D_func(x):
    return math.floor(A*x/B)-A*math.floor(x/B)
print(D_func(min(B-1,N)))
### BUGGY CODE ###

k=int(input())

if k%2==0 or k%5==0:
  print(-1)
  exit()

num=7
num%=k
ans=1

while k!=0:
  num=(10*num+7)%k+7

print(ans)

### FIXED CODE ###

k=int(input())

if k%2==0 or k%5==0:
  print(-1)
  exit()

if k%7==0:
  l=9*k//7
else:
  l=9*k

ans=1
q=10%l

while q!=1:
  q*=10
  q%=l
  ans+=1

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

n = int(input())
m = n

x = 1

for i in range(1, n - 1):
    for j in range(1, n):
        n = m
        n -= i
        if n % j == 0:
            x += 1
        else:
            x = x

print(x)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*(n-k+1)
r=1
for i in range(k):
    r=r*a[i]
ans[0]+=r
for i in range(1,n-k+1):
    ans[i]+=(ans[i-1]*a[i+k-1])//a[i-1]
for j in range(1,n-k+1):
    if ans[j]>ans[j-1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n-k):
  if a[k+i]>a[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
bridge = []
for i in range(M):
    A, B = [int(i) for i in input().split()]
    bridge.append([A, B])

bridge = bridge[::-1]
ans_rev = [N*(N-1)//2]
G = []
combi = 0
for i in range(M-1):
    A, B = bridge[i]
    g_A = -1
    g_B = -1
    for j, g in enumerate(G):
        if A in g:
            g_A = j
        if B in g:
            g_B = j
    if g_A == -1 and g_B == -1:
        G.append([A, B])
        combi += 1
    elif g_A == -1:
        combi += len(G[g_B])
        G[g_B].append(A)
    elif g_B == -1:
        combi += len(G[g_A])
        G[g_A].append(B)
    elif g_A != g_B:
        combi += len(G[g_A]) * len(G[g_B])
        G[g_A].extend(G[g_B])
        del G[g_B]
    ans_rev.append(N*(N-1)//2-combi)

ans = ans_rev[::-1]
print(*ans, sep="\n")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M = [int(i) for i in input().split()]
parent = [i for i in range(N+1)]
node_num = [1 for i in range(N+1)]
def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

bridge = []
for i in range(M):
    A, B = [int(i) for i in input().split()]
    bridge.append([A, B])

bridge = bridge[::-1]
ans_rev = [N*(N-1)//2]
combi = 0
for i in range(M-1):
    A, B = bridge[i]
    r_A = find(A)
    r_B = find(B)
    if r_A != r_B:
        parent[r_B] = r_A
        combi += node_num[r_B] * node_num[r_A]
        node_num[r_A] += node_num[r_B]
    ans_rev.append(N*(N-1)//2-combi)

ans = ans_rev[::-1]
print(*ans, sep="\n")
### BUGGY CODE ###

s = input()
count = 0
for i in range(10**(len(s))):
    if i % 13 == 5:
        flag = True
        i_str = str(i)
        if len(i_str) < len(s):
            i_str = "0" * (len(s) - len(i_str)) + i_str
        for j in range(len(s)):
            if s[j] == "?" or i_str[j] == s[j]:
                continue
            else:
                flag = False
                break
        if flag == True:
            count += 1
print(count % (10**9 + 7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
sys.setrecursionlimit(200000)
l=[None]*N
a=1
def hu(n,x):
    global a
    for i in s[n]:
        if l[i[0]]==None:
            l[i[0]]=x+i[1]
            hu(i[0],x+i[1])
        else:
            if x+i[1]!=l[i[0]]:
                a=0
for i in range(N):
    if l[i]==None:
        l[i]=0
        hu(i,0)
print("Yes" if a else "No")

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[[]for i in range(N)]
for i in range(M):
    L,R,D=map(int,input().split())
    s[L-1].append((R-1,D))
    s[R-1].append((L-1,-D))
sys.setrecursionlimit(200000)
l=[None]*N
a=1
def hu(n,x):
    global a
    for i in s[n]:
        if l[i[0]]==None:
            l[i[0]]=x+i[1]
            hu(i[0],x+i[1])
        else:
            if x+i[1]!=l[i[0]]:
                a=0
for i in range(N):
    if l[i]==None:
        l[i]=0
        hu(i,0)
print("Yes" if a else "No")
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    a[-1] = a[-1] // 2
    a.sort()
print(sum(a))

### FIXED CODE ###

from heapq import heappop,heappush,heapify

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-a for a in A]

heapify(A_minus)

for _ in range(M):
    heappush(A_minus, -((-heappop(A_minus)) // 2))
ans = -sum(A_minus)
print(int(ans))
### BUGGY CODE ###

a, b, k = map(int, input().split())

if a == 0 and b == 0:
  print(a, b)
  exit()

ans = 0
while a >= 1:
  for i in range(k - 1):
    a -= 1
    ans += 1
if b >= 1:
  for i in range(k - ans):
    b -= 1
    
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())

if a >= k:
  print(a - k, b)
elif a < k and b > k - a:
  print(0, (b - k + a))
else:
  print(0,0)
### BUGGY CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
   
fib = [0] * (N + 1)
if 1 in break_list:
    fib[1] = 0
else:
    fib[1] = 1
    
fib[0] = 1
for i in range(N - 1):
    if i + 2 in break_list:
        fib[i + 2] = 0
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )

### FIXED CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )
### BUGGY CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
p = l()

for i in range(n-k+1):
    a = p[i:i+k]
    if ans < sum(a):
        ans = sum(a)
        cnt = a

aa = 0
for j in cnt:
    aa += (j+1)/2

print(aa)


### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,k=I()
p = l()
x = list(itertools.accumulate(p))

if n==1:
    print((p[0]+1)/2)
    sys.exit()

if n==k:
    print((x[-1]+k)/2)
    sys.exit()

for i in range(1,n-k+1):
    ans = max(ans,x[i+k-1]-x[i-1])

print((ans+k)/2)
### BUGGY CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
        c=deque()    
        s=0
        c.append((i,j))
        #c.append(j)
        
        t=len(c)
        while t>0:
                s+=1
                t=len(c)
                for k in range(t):
                        m,n = c.popleft()
                        #n = c.popleft()
                        S[m][n]=s
                        for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                          if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                          if T[kk]==1:continue
                          if S[kk] == 0:
                            c.append(kk)
                            
                        
 
        #print(T)
        d = max(d,s)
        S=np.zeros_like(T,dtype=int)
        
print(d-2)

### FIXED CODE ###

from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)

b=0
ans=0
rs=set(s)
for i in range(m):
    if t[i] not in rs:
        print(-1)
        exit()
    ind=my_index(s[b:],t[i])
    if ind==-1:
        ind=my_index(s,t[i])+1
        ans+=n-b+ind
        b=ind
    else:
        ans+=ind+1
        b+=ind+1
print(ans)
    

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
dic={}
ans=0
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]=[i]
    else:
        dic[s[i]].append(i)
b=-1
for i in range(m):
    if t[i] not in dic:
        print(-1)
        exit()
    res=dic[t[i]]
    if res[-1]<=b:
        ans+=res[0]+1+(n-b-1)
        b=res[0]
    else:
        idx=bisect.bisect_right(res,b)
        ans+=res[idx]-b
        b=res[idx]
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) / (fractions.gcd(number, ans)))
    return ans

MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result = (result+lcms/arr)
result = result%MOD
print(round(result))

### FIXED CODE ###


from fractions import gcd
MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
result = 0
lcms = 1
for number in arrs:
    lcms = (((number * lcms)) //(gcd(number, lcms)))
for arr in arrs:
    result += (lcms//arr)
result = result%MOD
ans = str(result).replace('.0','')
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
mod=10**9+7

    
dp=[0]*(n+1)
dp[0]=1

a=[int(input()) for i in range(m)]

for i in range(1,n+1):
    if i in a:
        continue
    x=dp[i-1]
    if i>1:
        x+=dp[i-2]
    dp[i]=x%mod
print(dp[-1])


### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7

    
dp=[0]*(n+1)
dp[0]=1

a=set(int(input()) for i in range(m))

for i in range(1,n+1):
    if i in a:
        continue
    x=dp[i-1]
    if i>1:
        x+=dp[i-2]
    dp[i]=x%mod
print(dp[-1])
### BUGGY CODE ###

a, b, c = map(int, input().split())

for _ in range(c):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
  else:
    break
    
print(a, b)

### FIXED CODE ###

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

if 0 <= K < A:
    A -= K
elif A <= K <= A + B:
    B -= (K - A)
    A = 0
else:
    A = 0
    B = 0

print(A, B)
### BUGGY CODE ###

n = int(input())
pow = 1
for i in range(1,n+1):
    pow *= i
print(pow%(10**9+7))


### FIXED CODE ###

from math import factorial
print((factorial(int(input()))%(10**9+7)))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for i in range(n):
    ans[i]=a.count(i+1)
print('\n'.join(map(str,ans)))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for i in range(n-1):
    ans[a[i]-1]+=1
print(*ans,sep='\n')