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

h,w=map(int,input().split())
a=[]
ans=0
s=set()
from collections import deque
q=deque([])
l=[[10**10 for i in range(w)]for j in range(h)]
for i in range(h):
    p=input()
    a.append(p)
    for j in range(w):
        if p[j]=="#":
            q.append((i,j))
            l[i][j]=0
        else:
            s.add((i,j))

while s:
    i,j=q.popleft()
    if (i-1,j) in s:
        s.remove((i-1,j))
        q.append((i-1,j))
        l[i-1][j]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i+1,j) in s:
        s.remove((i+1,j))
        q.append((i+1,j))
        l[i+1][j]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i,j-1) in s:
        s.remove((i,j-1))
        q.append((i,j-1))
        l[i][j-1]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i,j+1) in s:
        s.remove((i,j+1))
        q.append((i,j+1))
        l[i][j+1]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    
print(ans)      






### FIXED CODE ###

h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="#"
            q.append((i+x,j+y,v+1))

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

def clear_maze(sx, sy, gx, gy, maze):
    INF = 100000000
    distance = [[INF for i in range(W)] for j in range(H)]
    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sy][sx] = 0
        while len(queue):
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < W and 0 <= ny and ny < H and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1
        return distance[gy][gx]
    return bfs()

H,W = (int(x) for x in input().split())
maze = ['']*H
max_distance = 0
for i in range(H):
  maze[i] = list(input())
  
dic = {}
for i in range(H*W):
  dic[i] = [i % W,i//W,0]
  
for i in range(H*W):
  sx,sy = dic[i][0],dic[i][1]
  s = maze[sy][sx]
  if s == '#':
    continue
  for j in range(H*W):
    gx,gy = dic[j][0],dic[j][1]
    g = maze[gy][gx]
    if (sx == gx and sy == gy) or g == '#' or dic[j][2] == 1:
        continue
    tmp_s = s
    tmp_g = g
    maze[sy][sx] = 'S'
    maze[gy][gx] = 'G'
    max_distance = max(max_distance,clear_maze(sx, sy, gx, gy, maze))
    maze[sy][sx] = tmp_s
    maze[gy][gx] = tmp_g
    dic[i][2] = 1
        
print(max_distance)
    

    

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)
### BUGGY CODE ###

#!/usr/bin/env python3
N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

B = []
C = []
for _ in range(M):
    b, c = map(int, input().rstrip().split())
    B.append(b)
    C.append(c)

Index = sorted(range(M), key=lambda i: C[i], reverse=True)

for index in Index:
    A.sort()
    count = 0
    for i, a in enumerate(A):
        if a < C[index] and count < B[index]:
            A[i] = C[index]
            count += 1
        if a >= C[index]:
            break

print(sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
N, M = map(int, input().rstrip().split())
A = list(map(int, input().rstrip().split()))

B = []
C = []
for _ in range(M):
    b, c = map(int, input().rstrip().split())
    B.append(b)
    C.append(c)

Index = sorted(range(M), key=lambda i: C[i], reverse=True)

sum = 0
A.sort()
for index in Index:
    if A and A[0] >= C[index]:
        break
    count = 0
    i = 0
    while True:
        if i >= len(A):
            break
        if A[i] < C[index] and count < B[index]:
            sum += C[index]
            A.pop(i)
            # print(A)
            count += 1
            continue
        if A[i] >= C[index] or count >= B[index]:
            break
        i += 1

if A:
    for a in A:
        sum += a

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

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

N = int(input())

a = [i for i in map(int, input().split())]

total = []
x = 0
skip_total = []
for i in range(N-1):
    total.append(abs(a[i] - x))
    skip_total.append(abs(a[i+1] - x))
    x = a[i]
skip_total.append(abs(x - 0))
total.append(abs(a[N-1] - x))
x = a[N-1]
total.append(abs(x - 0))

print(skip_total[0] + sum(total[2:]))
for i in range(1, N-1):
    print(sum(total[0:i]) + skip_total[i] + sum(total[i+2:]))
print(sum(total[0:N-1]) + skip_total[N-1])


### FIXED CODE ###

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

N = int(input())

a = [i for i in map(int, input().split())]

a = [0] + a + [0]

total = 0
for i in range(N+1):
    total += abs(a[i] - a[i+1])

for i in range(1, N+1):
    print(total + abs(a[i-1] - a[i+1]) - (abs(a[i-1] - a[i]) + abs(a[i] - a[i+1])))
### BUGGY CODE ###

N = int(input())
S = input()

#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

Slist = list(S)

count = 0
for i in range(len(Slist)+1):
    for j in range(i+1, len(Slist)):
        for k in range(j+1, len(Slist)):
            notEqualColor = Slist[i] != Slist[j] and Slist[j] != Slist[k] and Slist[k] != Slist[i]
            notEqualDistance = (j - i != k - j)

            if(notEqualColor and notEqualDistance):
                count += 1

print(count)


### FIXED CODE ###

import collections

N = int(input())
S = input()

CountRGB = collections.Counter(S)

ans = CountRGB["R"] * CountRGB["G"] * CountRGB["B"]

tmp = 0
for i in range(N-2):
    for j in range(i+1, N-1):

        if(2 * j - i > N - 1):
            break

        checker = []
        checker.append(S[i])
        checker.append(S[j])
        checker.append(S[2 * j - i])

        c = collections.Counter(checker)

        if(c["R"] == 1 and c["G"] == 1 and c["B"] == 1):
            tmp +=1

print(ans - tmp)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, S: str):
    ans = 0
    for i in range(1000):
        si = format(i, '03')

        idx = 0
        for j in range(len(S)):
            if idx < len(si) and si[idx] == S[j]:
                idx += 1

        if idx == len(si):
            ans += 1

    print(ans)
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32s


def solve(N: int, S: str):
    ans = 0
    for i in range(1000):
        si = format(i, '03')

        idx = 0
        for j in range(len(S)):
            if idx >= len(si):
                break
            elif si[idx] == S[j]:
                idx += 1

        if idx == len(si):
            ans += 1

    print(ans)
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, S)

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

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

def floor(t):
  return int(t)

x = 0
Ans_0 = 0
for i in range(N+1):
  Ans = floor(A * x / B) - A * floor(x / B)
  if Ans_0 < Ans:
    Ans_0 = Ans
  x = x + 1
  
print(Ans_0)

### FIXED CODE ###

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

def floor(t):
  return int(t)

Ans = floor(A * min(N, B-1) / B)
  
print(Ans)
### BUGGY CODE ###

import numpy as np
n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary_x = sorted(ary)
ary_y = sorted(ary,key=lambda x:(x[1],x[0]))
num = np.array(ary,dtype=float)
ans = float("Inf")

for xi in range(n):
    for xj in range(1,n):
        for yi in range(n):
            for yj in range(1,n):
                count = 0
                lx,rx = ary_x[xi][0],ary_x[xj][0]
                by,uy = ary_y[yi][1],ary_y[yj][1]

                for i in range(n):
                    if lx <= ary[i][0] <= rx and by <= ary[i][1] <= uy:
                        count += 1
                if count >= k:
                    ans = min(ans,(rx - lx) * (uy - by))
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(n)]
ary.sort()

ans = float("Inf")
for i in range(n-k+1):
    for j in range(k,n-i+1):
        xmin = ary[i][0]
        xmax = ary[i+j-1][0]
        ary_y = sorted(ary[i:i+j], key=lambda x: (x[1]))
        for l in range(len(ary_y)-k+1):
            ymin = ary_y[l][1]
            ymax = ary_y[l+k-1][1]
            ans = min(ans,(xmax - xmin) * (ymax - ymin))
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
numlist=[]
count=1
count2=0
num=0
for i in range(n):
    count2=a[count-1]
    if count2 in numlist =="True":
        break
    numlist.append(count2)
    count=count2
for i in range(len(numlist)):
    if numlist[i]==count2:
        num=i+1
        break
numlist2=numlist[num:]
if len(numlist)>k:
    print(numlist[k-1])
else:
    b=(k-num)%(len(numlist2))
    if b==0:
        print(numlist2[len(numlist2)-1])
    else:
        print(numlist2[b-1])


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=set([a[0]])
num1=a[0]
num2=1
l2=[]
def al(num):
    l1.add(num)
def n2(num5):
    return num5 in l1
for i in range(n):
    num1=a[num1-1]
    al(num1)
    if num2==len(l1):
        break
    else:
        num2=len(l1)
l1=list(l1)
num=l1.index(num1)
l2=l1[num:]
l1=l1[:num]
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
answers = []
for i in range(Q):
    l, r = map(int, input().split())
    answers.append(S[l-1:r].count('AC'))
for answer in answers:
    print(answer)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
data = [0] * (N+1)
for i in range(N):
    data[i+1] = data[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r =map(int, input().split())
    print(data[r-1] - data[l-1])
### BUGGY CODE ###

M = 1000000007
def pow(k):
    ans = 1
    for _ in range(k):
        ans *= 2
        ans %= M
    return ans

def main():
    n = int(input())
    a = list(map(int, input().split()))
    bit_size = len(bin(max(a))[2:])
    for i in range(n):
        a[i] = bin(a[i])[2:].zfill(bit_size)

    sum = 0
    for i in range(bit_size):
        one = 0
        zero = 0
        for j in range(n):
            if a[j][i] == '1':
                one += 1
            else: 
                zero += 1
        sum += pow(bit_size - i - 1) * (one % M) * (zero % M)
        sum %= M
    print(sum)

if __name__ == '__main__':
    main()

### FIXED CODE ###

M = 1000000007
def pow(k):
    ans = 1
    for _ in range(k):
        ans *= 2
        ans %= M
    return ans

def main():
    n = int(input())
    a = list(map(int, input().split()))
    bit_size = len(bin(max(a))[2:])
    for i in range(n):
        a[i] = bin(a[i])[2:].zfill(bit_size)

    sum = 0
    for i in range(bit_size):
        one = 0
        zero = 0
        for j in range(n):
            if a[j][i] == '1':
                one += 1
            else: 
                zero += 1
        sum += pow(bit_size - i - 1) * (one % M) * (zero % M)
        sum %= M
    print(sum)

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

import collections

class UnionFind:
    def __init__(self, n):
        self._id = list(range(n))
        self._sz = [1] * n

    def _root(self, i):
        j = i
        while (j != self._id[j]):
            self._id[j] = self._id[self._id[j]]
            j = self._id[j]
        return j

    def find(self, p, q):
        return self._root(p) == self._root(q)

    def union(self, p, q):
        i = self._root(p)
        j = self._root(q)
        if (self._sz[i] < self._sz[j]):
            self._id[i] = j
            self._sz[j] += self._sz[i]
        else:
            self._id[j] = i
            self._sz[i] += self._sz[j]

n, k, l = [int(x) for x in input().split()]
pqs = set(tuple(int(x) - 1 for x in input().split()) for _ in range(k))
rss = set(tuple(int(x) - 1 for x in input().split()) for _ in range(l))

road = UnionFind(n)
for pq in pqs:
    road.union(*pq)

rail = UnionFind(n)
for rs in rss:
    rail.union(*rs)

roadset = collections.defaultdict(set)
railset = collections.defaultdict(set)
for i in range(n):
    roadset[road._root(i)].add(i)
    railset[rail._root(i)].add(i)

print(' '.join([str(len(roadset[road._root(i)] & railset[rail._root(i)])) for i in range(n)]))


### FIXED CODE ###

import collections

class UnionFind:
    def __init__(self, n):
        self._id = list(range(n))
        self._sz = [1] * n

    def _root(self, i):
        j = i
        while (j != self._id[j]):
            self._id[j] = self._id[self._id[j]]
            j = self._id[j]
        return j

    def find(self, p, q):
        return self._root(p) == self._root(q)

    def union(self, p, q):
        i = self._root(p)
        j = self._root(q)
        if (self._sz[i] < self._sz[j]):
            self._id[i] = j
            self._sz[j] += self._sz[i]
        else:
            self._id[j] = i
            self._sz[i] += self._sz[j]

n, k, l = [int(x) for x in input().split()]
pqs = set(tuple(int(x) - 1 for x in input().split()) for _ in range(k))
rss = set(tuple(int(x) - 1 for x in input().split()) for _ in range(l))

road = UnionFind(n)
for pq in pqs:
    road.union(*pq)

rail = UnionFind(n)
for rs in rss:
    rail.union(*rs)

roadrail = [(road._root(i), rail._root(i)) for i in range(n)]
cnt = collections.Counter(roadrail)

print(' '.join([str(cnt[r]) for r in roadrail]))
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  turn = 2
  tmp=[]
  for i in s:
      tmp.append(i)
  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              tmp.append(c)
          else:
              tmp = [c] + tmp
  if turn == 2:
      print("".join(tmp))
  else:
      print("".join(tmp[::-1]))
main()


### FIXED CODE ###

def main():
  from collections import deque
  s=input()
  q=int(input())
  turn = 2
  d=deque(s)

  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              d.append(c)
          else:
              d.appendleft(c)
  if turn == 2:
      print("".join(d))
  else:
      print("".join(list(d)[::-1]))
main()
### BUGGY CODE ###

from collections import*
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

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

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])

def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

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

## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math


#計算量を無視して愚直に実装してみる
S = input() #文字列型で受け取る
N = len(S)
#print(len(S))

#5桁以上しか探索しないコード
sg = []
for i in range(N):
    j = 5
    while i+j <= N:
        sg.append([i, i+j])
        j += 1
#print(sg)
counter = 0
for i in range(len(sg)):
    s = S[sg[i][0]:sg[i][1]]
    if(int(s)%2019==0):
        counter += 1
print(counter)



'''
index = [i for i in range(len(S))]
combi = list(combinations(index, 2))
#print(combi)

counter = 0
for i in range(len(combi)):
    #print()
    #print('start:{},goal:{}'.format(combi[i][0], combi[i][1]+1))
    s = S[combi[i][0]:combi[i][1]+1]
    #print('s:{},s%2019:{}'.format(s, int(s)%2019))
    #print()
    if(int(s) % 2019 == 0):
        #print('hit')
        counter += 1
print(counter)
'''


'''
#実験1
def is_there_0(K):
    #文字列入力
    ret = 'No'
    for i in range(len(K)):
        if(K[i] == '0'):
            ret = 'Yes'
    return ret

for i in range(1000):
    if(is_there_0(str(2019*i)) == 'No'):
        print('i:{}, 2019*i:{}'.format(i, 2019*i))
'''




















'''
#実験2
l = []
for i in range(10000):
    l.append( (2019*i)%10000 )

l = sorted(l)
#print(l)
print(len(l))
'''


### FIXED CODE ###

## coding: UTF-8

S = input()[::-1] #文字列型で受け取る
N = len(S)
#print(S)

remainder = [0] * 2019
tmp = 0
rad = 1 # *10**(i) % 2019
for i in range(N):
    r = int(S[i])
    tmp += r*rad
    tmp %= 2019
    #print(tmp)
    remainder[tmp] += 1
    rad *= 10
    rad %= 2019

    #print(S[i:], int(S[i:])%2019)
    #remainder[int(S[i:])%2019]+= 1
remainder[0] += 1
#print(-1)



answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))
### BUGGY CODE ###

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

ans = []
for i in range(N):
    s_ = S[i:]
    tmp_ans = []
    for j in range(N, -1, -1):
        if j == 0:
            s = s_
        else:
            s = s_[:-j]

        tmp_ans += [s.count('AC')]
    ans += [tmp_ans]

for _ in range(Q):
    l, r = map(int, input().split())
    print(ans[l-1][r])

### FIXED CODE ###

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

t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
cnt = 0
for _ in range(n):
    for i in range(n-1):
        if A[i] > A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            cnt += 1
AA = A*2
nn = len(AA)
out_cnt = 0
for _ in range(nn):
    for i in range(nn-1):
        if AA[i] > AA[i+1]:
            AA[i], AA[i+1] = AA[i+1], AA[i]
            out_cnt += 1
ans = (k*cnt % MOD + out_cnt * (k*(k-1)//2) % MOD) % MOD
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
cnt = 0
for _ in range(n):
    for i in range(n-1):
        if A[i] > A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            cnt += 1
AA = A*2
nn = len(AA)
out_cnt = 0
for _ in range(nn):
    for i in range(nn-1):
        if AA[i] > AA[i+1]:
            AA[i], AA[i+1] = AA[i+1], AA[i]
            out_cnt += 1
ans = (k*cnt % MOD + out_cnt * (k*(k-1)//2) % MOD) % MOD
print(ans)
### BUGGY CODE ###

S = input()
T = input()

length = len(S)

ans = 0
pre = -1

for t in T:
    x = S.find(t, pre+1, length)
    if x != -1:
        ans += x - pre
        pre = x
    else:
        x = S.find(t, 0, pre+1)
        if x != -1:
            ans += length + x - pre
            pre = x
        else:
            ans = -1
            break

print(ans)

### FIXED CODE ###

S = input()
T = input()

length = len(S)

ans = 0
pre = -1

for t in T:
    x = S.find(t, pre+1, length)
    if x != -1:
        ans += x - pre
        pre = x
    else:
        x = S.find(t, 0, pre+1)
        if x != -1:
            ans += length + x - pre
            pre = x
        else:
            ans = -1
            break

print(ans)