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

import math
K = int(input())

count = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for q in range(1, K+1):
            count += math.gcd(math.gcd(i,j),q)
print(count)

### FIXED CODE ###

import math

K = int(input())

count = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            count += math.gcd(math.gcd(i,j), k)
print(count)
### BUGGY CODE ###

import collections

N=int(input())
ans=0
s=[input() for x in range(N)]


for i in range(N):
  for j in range(N):
    if i<j:
      if collections.Counter(s[i])==collections.Counter(s[j]):
        ans+=1
print(ans)

### FIXED CODE ###

import collections

N=int(input())
ans=0
s=[input() for x in range(N)]

d={}

for i in range(N):

  temp=str(sorted(s[i]))

  if temp in d.keys():
    ans+=d[temp]
    d[temp]+=1
  else:
    d[temp]=1

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
for i in range(n-1):
  if i+2 not in a:
    dp[i+2]=dp[i+1]+dp[i]
  else:
    dp[i+2]=0
print(dp[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[1]*(n+1)
dp[0]=1
dp[1]=1
for i in range(m):
  if a[i]==1:
    dp[1]=0
  else:
    dp[a[i]]=0
for i in range(2,n+1):
  if dp[i]:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))
### BUGGY CODE ###

N=int(input())
X=input()
Xnum=int(X,2)
popcount=X.count('1')
if popcount != 1:
    Xnum1=Xnum%(popcount-1)
Xnum0=Xnum%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - (2**(N-i-1)%(popcount-1)))%(popcount-1)
    else:
        Xi = (Xnum0 + (2**(N-i-1)%(popcount+1)))%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)

### FIXED CODE ###

N=int(input())
X=input()
popcount=X.count('1')
bi1=[]
bi0=[]
Xnum1 = 0
Xnum0 = 0
if popcount != 1:
    for i in range(N):
        if i==0: bi1.append(1)
        else: bi1.append(bi1[i-1]*2%(popcount-1))
        Xnum1 = (Xnum1 + int(X[N-i-1])*bi1[i])%(popcount-1)
for i in range(N):
    if i==0: bi0.append(1)
    else: bi0.append(bi0[i-1]*2%(popcount+1))
    Xnum0 = (Xnum0 + int(X[N-i-1])*bi0[i])%(popcount+1)
for i in range(N):
    if popcount==1 and X[i]=='1':
        print(0)
        continue
    if X[i]=='1':
        Xi = (Xnum1 - bi1[N-i-1])%(popcount-1)
    else:
        Xi = (Xnum0 + bi0[N-i-1])%(popcount+1)
    ans = 1
    while Xi!=0:
        Xi = Xi % bin(Xi).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

n = int(input())
print(n - 1)
s0 = str(input())
if s0 == 'Vacant':
    exit()
l = 0
r = n - 1
while abs(l - r) > 1:
    m = (l + r) // 2
    print(m)
    s = str(input())
    if s == 'Vacant':
        exit()
    else:
        if s0 != s:
            l = m
        else:
            r = m
        s0 = s
else:
    print(l)
    s = str(input())


### FIXED CODE ###

n = int(input())
l = 0
r = n - 1
print(l)
s_l = str(input())
if s_l == 'Vacant':
    exit()
while abs(l - r) > 1:
    m = (l + r) // 2
    print(m)
    s_m = str(input())
    if s_m == 'Vacant':
        exit()
    else:
        if (m - l) % 2:
            if s_m != s_l:
                l = m
                s_l = s_m
            else:
                r = m
                s_r = s_m
        else:
            if s_m != s_l:
                r = m
                s_r = s_m
            else:
                l = m
                s_l = s_m
else:
    print(r)
    s = str(input())
### BUGGY CODE ###

import math


def list_gcd(A):
    """N個の最大公約数
    Args:
        A (list[int])

    Returns:
        int: 最大公約数

    Examples:
        >>> list_gcd([1300, 34, 54, 60])
        2
    """
    ans = A[0]
    for i in range(1, len(A)):
        ans = math.gcd(ans, A[i])
    return ans


def resolve():
    K = int(input())

    ans = 0

    for kk in range(1, K+ 1):
        for jj in range(1, K+ 1):
            for ii in range(1, K+ 1):
                ans += list_gcd([kk, jj, ii])

    print(ans)


resolve()

### FIXED CODE ###

from math import gcd


def resolve():
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            a = gcd(i, j)
            for k in range(1, n + 1):
                ans += gcd(a, k)

    print(ans)


resolve()
### BUGGY CODE ###

from collections import deque
n=int(input())
a=[]
for i in range(n):
   a.append(int(input()))
q=deque(a)
for i in range(n):
    temp=q.popleft()
    print(max(q))
    q.append(temp)


### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
   a.append(int(input()))
b=sorted(a,reverse=True)
tempa=b[0]
tempb=b[1]
for i in range(n):
    if a[i]<tempa:
        print(tempa)
    else:
        print(tempb)
### BUGGY CODE ###

import bisect
def serach(target, array):
    l, r = -1, len(array)
    while r - l > 1:
        m = (l+r)//2
        if array[m] < target:
            l = m
        else:
            r = m
    return l, r

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

BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
ret = 0
for b, c in BC:
    r = bisect.bisect_left(A, c)
    # l, r = serach(c, A)
    if r <= 0:
        break
    b = min(b, r)
    ret += c * b
    A = A[b:]

print(sum(A)+ret)

### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
for i in range(M):
    b, c = map(int, input().split())
    A.append([b, c])

total = 0
D = []
A = sorted(A, key=lambda x:x[1], reverse=True)
for b, c in A:
    if len(D) >= N:
        break
    D.extend([c]*b)
print(sum(D[:N]))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i] < l[j] + l[k] and l[j] < l[i] + l[k] and l[k] < l[i] + l[j]:
                cnt += 1
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i - 1, 0, -1):
        c = l[i] - l[j]
        index = bisect.bisect_right(l, c, 0, j)
        cnt += j - index
print(cnt)
### BUGGY CODE ###

n=int(input())
l=[int(x) for x in input().split()]
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        for c in range(b+1,n):
            if abs(l[a]-l[b])<l[c] and l[c]<l[a]+l[b]:
                s=s+1
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()

ans = A[len(A) - 1] - A[0]
small = 0
large = len(A) - 1
while (A != []):

    if len(A) == 2:
        break
    elif len(A) == 3:
        ans += max(A[1] - A[0], A[2] - A[1])
        break
    ans += A[len(A) - 2] - A[0] + A[len(A) - 1] - A[1]
    A = A[1:-1]

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()

ans = A[len(A) - 1] - A[0]
small = 0
large = len(A) - 1
while (True):

    if large - small == 1:
        break
    elif large - small == 2:
        ans += max(A[large] - A[large - 1], A[small + 1] - A[small])
        break
    ans += A[large - 1] - A[small] + A[large] - A[small + 1]
    small += 1
    large -= 1

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

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[a[i][j] - b[i][j] for j in range(w)] for i in range(h)]

MAX_K = 80 * (h + w) + 5
dp = [[[False] * (MAX_K + 80) for _ in range(w)] for _ in range(h)]
dp[0][0][abs(c[0][0])] = True

for i in range(h):
    for j in range(w):
        for k in range(MAX_K):
            if dp[i][j][k]:
                if i < h - 1:
                    dp[i + 1][j][abs(k + c[i + 1][j])] = True
                    dp[i + 1][j][abs(k - c[i + 1][j])] = True

                if j < w - 1:
                    dp[i][j + 1][abs(k + c[i][j + 1])] = True
                    dp[i][j + 1][abs(k - c[i][j + 1])] = True

for k in range(MAX_K):
    if dp[h - 1][w - 1][k]:
        ans = k
        break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

CONST = 80 * 80 * 2
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1 << (c[0][0] + CONST)

for i in range(h):
    for j in range(w):
        if i < h - 1:
            dp[i + 1][j] |= (dp[i][j] << c[i + 1][j])
            dp[i + 1][j] |= (dp[i][j] >> c[i + 1][j])
        if j < w - 1:
            dp[i][j + 1] |= (dp[i][j] << c[i][j + 1])
            dp[i][j + 1] |= (dp[i][j] >> c[i][j + 1])

for k in range(CONST):
    if dp[h - 1][w - 1] & (1 << (CONST + k)) != 0 or dp[h - 1][w - 1] & (
            1 << (CONST - k)) != 0:
        ans = k
        break

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

# ABC073C - Write and Erase
n = int(input())
arr = []
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.pop(arr.index(m))
    else:
        arr += [m]
print(len(arr))

### FIXED CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = set()
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.remove(m)
    else:
        arr.add(m)
print(len(arr))
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = list(input())
print(len(set(list(combinations(S, 3)))))


### FIXED CODE ###

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

ans = 0

for i in range(10):
    if str(i) not in S:
        continue
    ind_i = S.index(str(i))
    for j in range(10):
        if str(j) not in S[ind_i+1:]:
            continue
        ind_j = S[ind_i+1:].index(str(j)) + ind_i+1
        for k in range(10):
            if str(k) in S[ind_j+1:]:
                ans += 1

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

from  heapq import heappush, heappop, heapify

n,m,s,t=map(int,raw_input().split())

nl=[ [ ] for j in range(n+1) ] 

for i in range(m):
	u,v,a,b=map(int,raw_input().split())
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#print nl

v=2


def dij(v,type):
	d=[ float("inf") for i  in range(n+1)]
	d[v]=0

	Q=[]
	heappush(Q,v)

	while len(Q)>0:
		u=heappop(Q)
		for v,yen,snuuk in nl[u]:
			if type=="y":alt=d[u]+yen
			elif type=="s":alt=d[u]+snuuk

			if d[v]> alt:
				d[v]=alt
				heappush(Q,v)
	return d

d_y=dij(s,"y")
d_s=dij(t,"s")

val=float("inf")

A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-1) % div + fib(n-2) % div
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)


### FIXED CODE ###

def main(N, M, a_list):
    div = 10**9 + 7

    a_set = set(a_list)
    
    dp = {}
    dp[0] = 1
    if 1 in a_set:
        dp[1] = 0
    else:
        dp[1] = 1

    for i in range(N):
        if i+2 in a_set:
            dp[i+2] = 0
        else:
            dp[i+2] = (dp[i+1] + dp[i])
    
    print(dp[N] % div)


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 10
for i in range(n-k+1):
  ans = min(ans, h[i:i+k][-1] - h[i:i+k][0])
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 10
for i in range(n-k+1):
  ans = min(ans, h[i+k-1] - h[i])
print(ans)
### BUGGY CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while p not in man:
        if ball >0:ball,man[a%n] =ball-1, man[a%n]+1
        elif ball == 0:ball,man[a%n] = man[a%n],ball
        a+=1
    print(man.index(max(man)))            

### FIXED CODE ###

while 1:
    n,p = map(int,input().split())
    if n==0:break
    man =  [0]*n
    ball,a = p,0
    while 1:
        a%=n
        if ball >0:
            ball-=1
            man[a]+=1
        elif ball == 0:ball,man[a] = man[a],ball
        if man[a]==p:break
        a+=1
    print(a)
### BUGGY CODE ###

import heapq
def SME(start,end):
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end//2):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
result = 0
p_t = [0]
for i in range(N):
    p_t.append(p[i]+p_t[i])
ans = p_t[K] - p_t[0]

for i in range(N-K):
    tmp = p_t[i+1+K] - p_t[i+1]
    if ans < tmp:
        ans = tmp
print((ans+K)/2)
### BUGGY CODE ###

from collections import deque

n = int(input())
a = input()
ans = deque()

for i in range(1,n+1):
    ans.append(a.count(str(i)))

for j in ans:
    print(j)


### FIXED CODE ###

from collections import deque

n = int(input())
a = list(map(int,input().split()))
ans = [0] * n

for i in a:
    ans[i-1] += 1

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

x = int(input())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


p = factorization(x)
# print(p)
Bas = 0
Aas = 0
for i in range(1):
    _p = p[i][0]
    # print(_p)
    B = 0
    flg = 0
    while True:

        xnew = (B + _p)**5 - B ** 5
        # print(xnew)
        if xnew == x:
            Bas = B
            Aas = B + _p
            break
        if xnew > x:
            if flg == -1:
                B *= 10
            else:
                B -= 1
            flg = -1
        else:
            if flg == 1:
                B *= 10
            else:
                B += 1
            flg = 1

print(f'{Aas} {Bas}')


### FIXED CODE ###

x = int(input())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


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


p = factorization(x)
p = make_divisors(x)
# print(p)
Bas = 0
Aas = 0

flg = False
# p.append([1, 1])
# print(p)
for i in range(len(p)):
    if flg:
        break
    _p = p[i]
    # print(_p)
    B = int(-_p/2)

    while True:

        xnew = (B + _p)**5 - B ** 5
        # print(B, xnew)
        if xnew == x:
            Bas = B
            Aas = B + _p
            flg = True
            break

        if xnew > x:
            break

        B += 1


print(f'{Aas} {Bas}')
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    minus = 0
    plus = 0
    fact = [0] * (N+1)
    fact[0] = 1
    fa = 1
    for i in range(1, N+1):
        fa *= i
        fact[i] = fa
    b = fact[K-1]
    for i in range(N-K+1):
        a = fact[N-i-1]
        c = fact[N-i-K]
        comb = (a*pow(b, mod-2, mod)*pow(c, mod-2, mod)) % mod
        minus += (A[i] * comb)
        plus += (A[-i-1] * comb)
    print((plus - minus) % mod)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
minus = 0
plus = 0
fact = [0] * (N+1)
fact[0] = 1
pow_fact = [0] * (N+1)
pow_fact[0] = 1
fa = 1
for i in range(1, N+1):
    fa *= i
    fa %= mod
    fact[i] = fa
    pow_fact[i] = pow(fa, mod-2, mod)
b = pow_fact[K-1]
for i in range(N-K+1):
    a = fact[N-i-1]
    c = pow_fact[N-i-K]
    comb = (a*b*c) % mod
    minus += (A[i] * comb) % mod
    plus += (A[-i-1] * comb) % mod
print((plus - minus) % mod)
### BUGGY CODE ###

x = input()
y = input()
lx = len(x)
ly = len(y)

lcs = [[''] * (ly + 1) for _ in range(lx + 1)]
for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            lcs[i_x+1][i_y+1] = lcs[i_x][i_y] + x[i_x]
        else:
            lcs[i_x+1][i_y+1] = max(lcs[i_x+1][i_y], lcs[i_x][i_y+1], key=len)

print(lcs[-1][-1])


### FIXED CODE ###

x = input()
y = input()
lx = len(x)
ly = len(y)

chars = [[''] * (ly + 1) for _ in range(lx + 1)]
length = [[0] * (ly + 1) for _ in range(lx + 1)]
prev = [[0b00] * (ly + 1) for _ in range(lx + 1)]

for i_x in range(lx):
    for i_y in range(ly):
        if x[i_x] == y[i_y]:
            length[i_x+1][i_y+1] = length[i_x][i_y] + 1
            chars[i_x+1][i_y+1] = x[i_x]
            prev[i_x+1][i_y+1] = 0b11
        elif length[i_x+1][i_y] > length[i_x][i_y+1]:
            length[i_x+1][i_y+1] = length[i_x+1][i_y]
            prev[i_x+1][i_y+1] = 0b01
        else:
            length[i_x+1][i_y+1] = length[i_x][i_y+1]
            prev[i_x+1][i_y+1] = 0b10

lcs = [''] * length[-1][-1]
i_x, i_y = lx, ly
i = 1
while i_x and i_y:
    if prev[i_x][i_y] == 0b11:
        lcs[-i] = chars[i_x][i_y]
        i += 1
    i_x, i_y = i_x - ((prev[i_x][i_y] & 0b10) >> 1), i_y - (prev[i_x][i_y] & 0b01)

print(''.join(lcs))
### BUGGY CODE ###


s = list(input())
t = input()
tmp=0
ans=0
flag=True
for ch in t:
    if ch in s:
        while ch != s[tmp]:
            ans += 1
            tmp = (tmp+1)%len(s)
        ans += 1
        tmp = (tmp+1)%len(s)
    else:
        flag = False
        break

if flag:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import collections
import bisect

d = collections.defaultdict(list)
s = input()
t = input()
for i,S in enumerate(s,1):
    d[S].append(i)
k=0
ans=0
for ch in t:
    l = d[ch]
    if len(l)==0:
        print(-1)
        exit(0)
    if l[-1]<=ans:
        ans=l[0]
        k+=1
    else:
        ans=l[bisect.bisect_right(l,ans)]

print(len(s)*k+ans)
### BUGGY CODE ###

#2
k = 0
x = int(input())
for y in range(0, x+1):
    y = y*y
    if y <= x:
        k = y
print(k)
        
        

### FIXED CODE ###

#2
n = int(input())
print(int(n**(1/2))**2)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]
 
answer = 0
tmp = deque()
 
for i in range(M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = deque(C[i])
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        elif len(right) != 0:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = []
heapq.heapify(tmp)

for i in range(M+1):
    if i in C:
        right = C[i]
        for j in right:
            heapq.heappush(tmp,-1*j)
        
    if tmp != []:
        answer += -1*heapq.heappop(tmp)
print(answer)