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

import sys
sys.setrecursionlimit(10**9)
N,M = map(int, input().split())
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [-1] * (N+1)
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

def root(x):
    if data[x] == x:
        return x
    else:
        r = root(x)
        diff_weight[x] += diff_weight[ data[x] ]
        data[x] = r
        return r

def weight(x):
    _ = root(x)
    return diff_weight[x]


def diff(x,y):
    return weight(y) - weight(x)

def merge(x,y,w):
    w  += weight(x); w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y: return False
    if rank[x] < rank[y]: x,y = y,x; w = -w
    if rank[x] == rank[y]: rank[x] += 1
    data[y] = x
    diff_weight[y] = w
    return True

def issame(x,y):
    return root(x) == root(y)

for i in range(M):
    L,R,D = LRD[i]
    if not issame(L,R):
        merge(L,R,D)
    else:
        if weight(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")

    
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
input = sys.stdin.readline
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [x for x in range(N+1)]
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

def root(x):
    if data[x] == x:
        return x
    else:
        r = root( data[x] )
        diff_weight[x] += diff_weight[ data[x] ]
        data[x] = r
        return r

def weight(x):
    # _ = root(x)
    return diff_weight[x]


def diff(x,y):
    return weight(y) - weight(x)

def merge(x,y,w):
    w  += weight(x); w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y: return False
    if rank[x] < rank[y]: x,y = y,x; w = -w
    if rank[x] == rank[y]: rank[x] += 1
    data[y] = x
    diff_weight[y] = w
    return True

def issame(x,y):
    return root(x) == root(y)

for i in range(M):
    L,R,D = LRD[i]
    # print(L,R,D)
    if not issame(L,R):
        _  = merge(L,R,D)
    else:
        if diff(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")
### BUGGY CODE ###

MOD = int(1e9) + 7

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
b = [1]*(n+1)
for i in range(1,n+1):
    b[i] = b[i-1]*i
for i in range(k+1):
    if n-i-1<k-1:
        break
    c = b[n-1-i]//(b[k-1]*b[n-i-k])
    ans += c*a[n-1-i]
    ans -= c*a[i]
    ans = ans%MOD
print(ans)

### FIXED CODE ###

import math
n_ = 10**5 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
for i in range(N-K+1):
    count=(count+((A[i]-A[N-1-i])*nCr(N-i-1,K-1)))%(10**9+7)
print(count)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
maxx = n//b
ans = 0
for i in range(min(maxx,10**9)):
    x = b*(maxx-i)-1
    ans = max(math.floor(a*x/b)-a*(math.floor(x/b)),ans)
ans = max(math.floor(a*n/b)-a*(math.floor(n/b)),ans)
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n) #上記よりxとしてmin(B-1,N)を選ぶのが最善
print((a*x)//b-a*(x//b))
### BUGGY CODE ###

s = str(input())
t = str(input())

for i in range(len(s)):
  if s[i] != t[i]:
    x = s[i]
    #print(s[i],t[i])
    s = s.replace(t[i], "#").replace(s[i], t[i]).replace("#", x)
    #print(s)
  if s == t:
    print("Yes")
    quit()
    
if s == t:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = str(input())
T = str(input())

exchange = [-1] * 26
alpha2num = lambda c: ord(c) - ord('a')
#print(alpha2num('y')) #==> 24

for i in range(len(S)):
    now_num = alpha2num(S[i])
    #print(now_num, exchange[now_num], alpha2num(T[i]))
    if exchange[now_num] == -1:
      exchange[now_num] = alpha2num(T[i])
    elif exchange[now_num] == alpha2num(T[i]):
      #print("yeee")
      continue
    else:
      print("No")
      quit()
  #print(exchange)    
  
exchange = sorted(exchange)
for i in range(1, 26):
  if exchange[i] == exchange[i - 1]:
    if exchange[i] != -1:
      print("No")
      quit()
  
print("Yes")
### BUGGY CODE ###

K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = n[1]+1
    n2 = n[0]
    for i in range(n[0], n[1]+1):
        if i%a!=0:
            continue
        if i<n1:
            n1 = i
        if i>n2:
            n2 = i
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")


### FIXED CODE ###

K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = (n[0]//a+(1 if n[0]%a>0 else 0))*a
    n2 = (n[1]//a)*a
    # print([n,n1,n2,a])
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")
### BUGGY CODE ###

n, x, y = map(int, input().split())
for k in range(1, n):
    min_combi_set = list()
    for i in range(1, n+1):
        for j in range(1, i):
            min_distance = min(abs(i-j), abs(x-i) + 1 + abs(j-y),abs(y-i) + 1 + abs(x-j))
            if min_distance == k:
                min_combi_set.append({i, j})
    print(len(min_combi_set))


### FIXED CODE ###

n, x, y = map(int, input().split())

count = {k:0 for k in range(1, n)}
for i in range(1, n+1):
    for j in range(1, i):
        k = min(abs(i-j), abs(x-i) + 1 + abs(j-y),abs(y-i) + 1 + abs(x-j))
        count[k] += 1
for i in count.values():
    print(i)
### BUGGY CODE ###

n=10**100
n5=10
n20=50
s=list(input())
ls=len(s)

sisr=[]
for ss in s:
  if ss=="R":
    sisr.append(True)
  else:
    sisr.append(False)

r=[-1]*ls
for ii in range(ls):
  iii=ii
  for jj in range(n5):
    if sisr[iii]:
      iii+=1
    else:
      iii-=1
  r[ii]=iii
    
import copy
r2=copy.copy(r)
for kk in range(n20):
  r4=[-1]*ls
  for ii in range(ls):
    iii=ii
    for jj in range(n5):
      iii=r2[iii]
    r4[ii]=iii
  r2=copy.copy(r4)
    
r3=[0]*ls
for ii in range(ls):
  r3[r2[ii]]+=1
#print(*r)
#print(*r2)
print(*r3)

### FIXED CODE ###

s=list(input())
ls=len(s)
r=[0]*ls
c=0
for ii in range(ls-1):
  if s[ii]=="R" and s[ii+1]=="R":
    c+=1
  elif s[ii]=="R" and s[ii+1]=="L":
    c+=1
    r[ii]+=c//2+c%2
    r[ii+1]+=c//2
    c=0
  elif s[ii]=="L" and s[ii+1]=="L":
    pass
  elif s[ii]=="L" and s[ii+1]=="R":
    pass
  #print(c)
#print(*r)
c=0  
for jj in range(ls-1):
  ii=ls-1-jj
  if s[ii-1]=="R" and s[ii]=="R":
    pass
  elif s[ii-1]=="R" and s[ii]=="L":
    c+=1
    r[ii-1]+=c//2
    r[ii]+=c//2+c%2
    c=0
  elif s[ii-1]=="L" and s[ii]=="L":
    c+=1
  elif s[ii-1]=="L" and s[ii]=="R":
    pass
  #print(ii,c)
print(*r)
### BUGGY CODE ###

import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add(j)
    s,t=map(int,inp().split())
    cache_kenken={}
    cache_kenkenpa={}
    def kenken(v):
        if v not in cache_kenken:
            cache_kenken[v]=[v2 for v1 in G[v] for v2 in G[v1]]
        return cache_kenken[v]
    def kenkenpa(v):
        if v not in cache_kenkenpa:
            cache_kenkenpa[v]=[v3 for v2 in kenken(v) for v3 in G[v2]]
        return cache_kenkenpa[v]
    visited={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            #print('{}:{}->{}'.format(step,u,v))
            if v==t:
                return step+1
            if v not in visited:
                heapq.heappush(que,(step+1,v))
                visited.add(v)
    return -1
print(sol())

### FIXED CODE ###

import heapq
def sol(inp=input):
    s=3
    n,m=map(int,inp().split())
    G={(i+1,j):set() for i in range(n) for j in range(s)}
    for _ in range(m):
        u,v=map(int,inp().split())
        for i in range(s):
            G[(u,i)].add((v,(i+1)%s))
    s,t=map(int,inp().split())
    visited={(s,0)}
    que=[]
    heapq.heappush(que,(0,(s,0)))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in G[u]:
            if v not in visited:
                visited.add(v)
                heapq.heappush(que,(step+1,v))
            if v==(t,0):
                return (step+1)//3
    return -1
print(sol())
### BUGGY CODE ###

S = input()
Q = int(input())
inversion_flg = False
# L = [input().split() for _ in range(Q)]

for i in range(Q):
    L = input().split()
    if L[0] == '1':
        if inversion_flg:
            inversion_flg = False
        else:
            inversion_flg = True
    # if L[0] == '2':
    else:
        if not inversion_flg:
            if L[1] == '1':
                S = L[2] + S
            else:
                S = S + L[2]
        else:
            if L[1] == '2':
                S = L[2] + S
            else:
                S = S + L[2]



# print(L)
if not inversion_flg: 
    print(S)
else:
    # S.reverse()
    S = S[::-1]
    print(S)

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

n, m = map(int, input().split())
s = [int(input()) for _ in range(m)]


dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, n + 1):
    if i not in s:
        x = dp[i - 1]
        if i > 1:
            x += dp[i - 2]
        dp[i] = x % MOD

print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
s = [int(input()) for _ in range(m)]
s.append(n+1)

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

for i in range(n - 1):
    dp[i + 2] = dp[i + 1] + dp[i]
mae = 0
ans = 1
for i in s:
    if i == mae:
        ans=0
    else:
        ans *= dp[i - 1 - mae]

    mae = i + 1
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

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

table = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    table[a-1][b-1] += 1

s = [[table[i][0]] for i in range(n)]

for i in range(n):
    for j in range(1, n):
        s[i].append(s[i][-1]+table[i][j])

for _ in range(q):
    i, j = map(int, input().split())
    tmp = 0
    if i == 1:
        for k in range(i-1, j):
            tmp += s[k][j-1]
    else:
        for k in range(i-1, j):
            tmp += s[k][j-1] - s[k][i-2]
    print(tmp)



'''
for i in range(n):
    for j in range(1, n):
        table[i][j] += table[i][j-1]

for i in range(n-1, 0, -1):
    for j in range(n):
        table[i-1][j] += table[i][j]

for i, j in y:
    print(table[i-1][j-1])
'''


### FIXED CODE ###

n, m, q = map(int, input().split())
x = [tuple(map(int, input().split())) for _ in range(m)]
y = [tuple(map(int, input().split())) for _ in range(q)]

table = [[0]*n for _ in range(n)]

for i, j in x:
    table[i-1][j-1] += 1

for i in range(n):
    for j in range(1, n):
        table[i][j] += table[i][j-1]

for i in range(n-1, 0, -1):
    for j in range(n):
        table[i-1][j] += table[i][j]

for i, j in y:
    print(table[i-1][j-1])
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.zeros(n, dtype=np.int64)
for i in range(n):
    a[i] = int(input())
for i in range(n):
    max1 = 0
    max2 = 0
    if len(a[:i]) != 0:
        max1 = np.max(a[:i])
    if len(a[i+1:]) != 0:
        max2 = np.max(a[i+1:])
    print(max(max1, max2))


### FIXED CODE ###

n = int(input())
max1 = 0
max2 = 0
index = 0
for i in range(n):
    a = int(input())
    new_max = max(a, max1)
    if (a == new_max and max2 <= max1) or (a == new_max and max2 <= max1 and a == max1):
        max2 = max1
        index = i
    elif (a != new_max and max2 <= a) or (a != new_max and max2 <= a and a == max1):
        max2 = a
    max1 = new_max

for i in range(n):
    if i != index:
        print(max1)
    else:
        print(max2)
### BUGGY CODE ###

N = int(input())  #数字
S = list(input()) #スペース抜きの複数行,１文字ずつ

cou = 0
for i in range(N):
    for j in range(i, N):
        if S[i] != S[j]:
            for k in range(j, N):
                if S[i] != S[k] and S[j] != S[k]:
                    if j - i != k - j:
                        cou +=1
print(cou)

### FIXED CODE ###

N = int(input())  #数字
S = list(input()) #スペース抜きの複数行,１文字ずつ

cou = 0

for i in range(0,N):
    j = 1
    while i + (2 * j) <= N-1:
        if S[i] != S[i + j] and S[i + j] != S[i + (2*j)] and S[i] != S[i + (2*j)]:
            cou += 1
        j += 1

print(S.count("R")*S.count("G")*S.count("B")-cou)
### BUGGY CODE ###

l, r = [int(x) for x in input().split()]

ans = 2200
for i in range(l, r):
    if i % 2019 == 0:
        pass
    else:
        for j in range(l+1, r+1):
            if i == j:
                continue
            elif j % 2019 == 0:
                continue
            else:
                tmpans = (i * j) % 2019
            ans = min(ans, tmpans)


print(ans)

### FIXED CODE ###

l, r = [int(x) for x in input().split()]

ans = 2200
for i in range(l, r):
    if i % 2019 == 0:
        ans = 0
        break
    else:
        for j in range(i+1, r+1):
            if i == j:
                continue
            elif j % 2019 == 0:
                ans = 0
                break
            else:
                tmpans = (i * j) % 2019
            ans = min(ans, tmpans)


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

n,q = map(int,input().split())
s = input()
ans = []
for i in range(q):
    l,r = map(int,input().split())
    count = 0
    s_1 = s[l-1:r]
    for i in range(len(s_1)-1):
        if s_1[i]=="A":
            if s_1[i+1]=="C":
                count += 1
    ans.append(count)
#ここから出力
for i in ans:
    print(i)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ac = [0 for i in range(n+1)]
ans = []
for i in range(len(s)-1):
    if s[i:i+2]=="AC":
        ac[i+1] = ac[i] + 1
    else:
        ac[i+1] = ac[i]

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

import sys
import numpy as np
from functools import lru_cache
input = sys.stdin.readline

sys.setrecursionlimit(1000000)

N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])

XH.sort(key=lambda xh: xh[0])
XH = np.array(XH, dtype=np.int64)

ans = 0 
while len(XH)>0:
	TRAGET = (XH[:,0] <= XH[0][0]+2*D)
	H = XH[0][1]
	if(0==H%A):
		a = H//A
	else:
		a = H//A+1
	XH[TRAGET] = XH[TRAGET] - [0,a*A]
	ans += a
	TRAGET = (XH[:,1] > 0)
	XH = XH[TRAGET]
print(ans)

### FIXED CODE ###

import sys
from collections import deque
 
input = sys.stdin.readline
 
N,D,A = map(int,input().split())
XH = []
for i in range(N):
	x,h = map(int, input().split())
	XH.append([x,h])
 
XH.sort(key=lambda xh: xh[0])
que = deque()
D = 2*D
 
H = XH[0][1]
if(0==H%A): a = H//A
else: a = H//A+1
que.append([XH[0][0]+D,a*A])
tot = a * A
ans = a
for i in range(1,N):
	while XH[i][0] > que[0][0] :
		tot -= que[0][1]
		que.popleft()
		if(len(que)==0): break
	if(tot < XH[i][1]):
		H = XH[i][1]-tot
		if(0==H%A): a = H//A
		else: a = H//A+1
		ans += a
		que.append([XH[i][0]+D,a*A])
		tot += a*A
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(n):
        dx,dy = xy[j]
        if uy < dy:
            continue
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

import itertools
import numpy as np

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())

cnt = 0
i = 2
a = prime_factorize(n)
if len(a) == 1:
    a.append(1)
b = []
for i in range(1,len(a)+1):
    b.append(list(itertools.combinations(a, i)))

m1 = 10**12
m2 = 10**12
for i in range(len(b)):
    for j in range(len(b[i])):
        c = np.prod(b[i][j])
        d = n // c
        if m1+m2 > c+d:
            m1 = c
            m2 = d

print(m1+m2-2)

### FIXED CODE ###

import sys

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()
    return divisors


n = int(input())
a = make_divisors(n)
#print(a)
ans = sys.maxsize
for x in a:
    y = n // x
    #print(x, y, x+y)
    ans = min(ans, x + y - 2)
print(ans)
### BUGGY CODE ###

A, B ,N = map(int,input().split())
if B-1 <= N:
    print(A*(B-1)//B)
else:
    ans = 0
    for x in range(1,N+1):
        ans_candidate = (A*x)//B- A*(x//B)
        if ans < ans_candidate:
            ans = ans_candidate
    print(ans)


### FIXED CODE ###

A, B ,N = map(int,input().split())
if B-1 <= N:
    print(A*(B-1)//B)
else:
    print(A*N//B)
### BUGGY CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(80*(x+y)):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

for k in range(80*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()


### FIXED CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
x=1
cnt=0
while True:
    x=a[x-1]
    cnt+=1
    if x==2:
        print(cnt)
        break
    elif x==1:
        print('-1')
        break
    else:
        continue


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
x=1
cnt=0
y=[1]
while True:
    x=a[x-1]
    cnt+=1
    y.append(x)
    if x==2:
        print(cnt)
        break
    elif x==1:
        print('-1')
        break
    elif cnt==100000:
        print(-1)
        break
    else:
        continue
### BUGGY CODE ###

N=int(input())
for n in range(1,3501):
    for w in range(1,3501):
        if n*(4*w-N)-N*w==0:
            continue
        if N*n*w % (n*(4*w-N)-N*w) ==0:
            h= (N*n*w) // (n*(4*w-N)-N*w)
            if h>=1:
                print(h,n,w)
                exit()


### FIXED CODE ###

N=int(input())
for n in range(1,3501):
    for w in range(1,3501):
        if n*(4*w-N)-N*w==0:
            continue
        if N*n*w % (n*(4*w-N)-N*w) ==0:
            h= (N*n*w) // (n*(4*w-N)-N*w)
            if h>=1:
                print(h,n,w)
                exit()
### BUGGY CODE ###

s = str(input())
t= str(input())

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)

### FIXED CODE ###

s = str(input())
t= str(input())

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)