Harryxun/stf_run huggingface dataset:
ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    s = input()
    if len(s) == 0:
        break
    flag = False
    for i in ok:
        if s[i[0]] == s[i[1]] == s[i[2]]:
            print(s[i[0]])
            flag = True
            break
    if flag:
        continue
    print("d")

### FIXED CODE ###

ok = [[0,4,8], [2,4,6], [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8]]
while True:
    try:
        s = input()
    except EOFError:
        break
    flag = False
    for i in ok:
        if s[i[0]] == s[i[1]] == s[i[2]] and s[i[0]] != 's':
            print(s[i[0]])
            flag = True
            break
    if flag:
        continue
    print("d")
N, M = map(int, input().split())
H = list(map(int, input().split()))

L = [0 for in range(N+1)]

for q in range(M):
  A, B = map(int, input().split())
  if H[A] < H[B]:
    L[A] += 1
  elif H[A] > H[B]:
    L[B] += 1
  else:
    L[A] += 1
    L[B] += 1
    
ans = 0
for i in range(1,N+1):
  if L[i] == 0:
    ans += 1
print(ans)


### FIXED CODE ###

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

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

for q in range(M):
  A, B = map(int, input().split())
  if H[A-1] < H[B-1]:
    L[A] += 1
  elif H[A-1] > H[B-1]:
    L[B] += 1
  else:
    L[A] += 1
    L[B] += 1
    
ans = 0
for i in range(1,N+1):
  if L[i] == 0:
    ans += 1
print(ans)
el,dl = map(int,input().split())
es=list(input.split()).sorted()
ds=[]
for _ in range(dl)
  d = map(int,input().split())
  ds.append(d)
ds.sort(key=lambda d: -d[1])
fs=[]
for b,c in ds:
  for _ in b:
    fs.append(c)
re=0
for ei in range(el):
  re += max(es[ei],fs[ei])
print(re)

### FIXED CODE ###

el,dl = map(int,input().split())
es=list(map(int,input().split()))
es.sort()
#print(es)
ds=[]
for _ in range(dl):
  d = list(map(int,input().split()))
  ds.append(d)
ds.sort(key=lambda d: -d[1])
#print(ds)
fs=[]
for b,c in ds:
  for _ in range(b):
    fs.append(c)
  if len(fs)>el:
    break
re=0
for ei in range(el):
  if ei>=len(fs):
    re += es[ei]
  else:
    re += max(es[ei],fs[ei])
print(re)
import numpy as np
A = []
for i in range(3):
    A.append(list(map(int, input().split())))
A = np.array(A)

N = int(input())
 
for n in range(N):
    called_num = int(input())
    exist_list = [called_num in A[i] for i in range(3)]
    if True in exist_list:
      	called_row = exist_list.index(True)
       	A[called_row] = [0 if x==called_num else x for x in A[called_row]]
    
sum_row = np.sum(A, axis=1)
sum_col = np.sum(A, axis=0)
sum_diag1 = np.diag(A).sum()
sum_diag2 = A[0][2] + A[1][1] + A[2][0] #良い実装が思いつかなかった
 
if 0 in sum_row or 0 in sum_col or 0 in [sum_diag1, sum_diag2]: #書き方イマイチ
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import numpy as np
A = []
for i in range(3):
    A.append(list(map(int, input().split())))
A = np.array(A)

N = int(input())

for n in range(N):
    called_num = int(input())
    exist_list = [called_num in A[i] for i in range(3)]
    if True in exist_list:
        called_row = exist_list.index(True)
        A[called_row] = [0 if x==called_num else x for x in A[called_row]]
        
sum_row = np.sum(A, axis=1)
sum_col = np.sum(A, axis=0)
sum_diag1 = np.diag(A).sum()
sum_diag2 = A[0][2] + A[1][1] + A[2][0] #良い実装が思いつかなかった

if 0 in sum_row or 0 in sum_col or 0 in [sum_diag1, sum_diag2]: #書き方イマイチ
    print('Yes')
else:
    print('No')
l=[0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
for i in range(int(input)-1,0,-1):
	if l[i]==1:print(i);break

### FIXED CODE ###

from collections import defaultdict

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

x = readInt()
l = [0]*(x+1)
l[1]=1

for i in range(2,len(l)):
  if l[i]==0:
    j = i*i
    while 1:
      if j>len(l)-1:
        break
      else:
        l[j]=1
        j*=i


for i in range(len(l)-1,-1,-1):
  if l[i]==1:
    print(i)
    break
N = int(input().split())
S = []
for _ in range(N):
    keihin = input().split()
    if keihin not in S:S.append(keihin)

print(len(S))

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

print(len(set(S)))
a, b = map(int, input().split())

print((a+b)//2 if (a+b)% == 0 else 'IMPOSSIBLE')

### FIXED CODE ###

a, b = map(int, input().split())
     
if (a + b) / 2 == (a + b) // 2:
	print(int((a + b) / 2))
else:
	print('IMPOSSIBLE')
N=int(input())
L=list(map(int,input().split()))
A=1
for i in range(N):
  A=A*L[i]
  if 10**18<A:
  print(-1)
  exit()
print(A)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
A=1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  A=A*L[i]
  if 10**18<A:
    print(-1)
    exit()
print(A)
A = input()
B = A.split()
a = int(B[0])
b = int(B[1])
c = int(B[2])
d = int(B[3])

if a <= 0 and b <= 0 and c <= 0 and d <= 0:
    print(a*c)
elif a > 0 and b > 0 and c > 0 and d > 0:
    print(b*d)
elif a > 0 and b > 0 and c<=0 and d<=0:
    print(a*d)
elif a<=0 and b<=0 and c>0 and d>0:
    print(b*c)
elif a<=0 and b<=0 and c<=0 and d>0:
    print(a*c)
elif a>0 and b>0 and c<=0 and d>0:
    print(b*d)
elif a <= 0 and b > 0:
    if c <= 0 and d > 0:
        if -c <= d and -a <= b:
            print(d*b)
        elif -c <= d and -a > b:
            if a*c > b*d:
                print(a*c)
            elif a*c <= b*d:
                print(b*d)
        elif -c > d and -a <= b:
            if a*c > b*d:
                print(a*c)
            elif a*c <= b*d:
                print(b*d)
        elif -c > d and -a > b:
            print(a*c)
    elif c> 0 and d <= 0:
        print()
    elif c<=0 and d<=0:
        print(a*c)

### FIXED CODE ###

x = int(input())
if x == 1:
    print(0)
elif x == 0:
    print(1)
import math
A, B, N = map(int, input().split())

if (B > N+1):
  x = N
  print((A*x)//B-A*(x//B))
else:
  x = N-N%(B-1)
  print((A*x)//B-A*(x//B))

### FIXED CODE ###

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

if (B == 1):
  print(0)
elif (B > N+1):
  x = N
  print((A*x)//B-A*(x//B))
else:
  x = N-N%(B-1)
  print((A*x)//B-A*(x//B))
n = int(input())
s = input()
ans = "No"
if n % 2 == 0:
    ans = "Yes"
    for i in range(n / 2):
        if s[i] != s[n / 2 + i]:
            ans = "No"
            break
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = "No"
if n % 2 == 0:
    ans = "Yes"
    for i in range(n // 2):
        if s[i] != s[n // 2 + i]:
            ans = "No"
            break
print(ans)
a = list(input().split())
a.replace("1","99")
if int(a[0]) > int(a[1]):
  print("Bob")
elif int(a[0]) == int(a[1]):
  print("Draw")
else:
  print("Alice")


### FIXED CODE ###

a = list(map(int,input().split()))
if a[0] == a[1]:
  print("Draw")
elif (a[0] == 1 or a[0] >= a[1]) and a[1] !=1:
  print("Alice")
else:
  print("Bob")
from collections import deque
import bisect
import sys


N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]

routes = [[] for _ in range(N)]

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)

lis = [10e+100 for _ in range(N)]
shortest = [10e+100 for _ in range(N)]
shortest[0] = 0
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            shortest[route] = shortest[checking]+1
            seen[route] = True
            function(route) 
    lis[insert_posi] = preserved
    return
        
function(0)

[print(i) for i in (minimum)]

### FIXED CODE ###

from collections import deque
import bisect
import sys

sys.setrecursionlimit(200000)

N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]
shortest = [10e+10 for _ in range(N)]
shortest[0] = 0

routes = [[] for _ in range(N)]

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            seen[route] = True
            shortest[route] = shortest[checking]+1
            function(route)
    lis[insert_posi] = preserved
    return
        
function(0)

[print(x) for x in minimum]
A = int(input())
print('%h:%m:%s' %(A/3600,A%3600/60,A%60))


### FIXED CODE ###

A = int(input())
print("%d:%d:%d"%(A/3600,(A%3600)/60,A%60))
x = input()
print x**3

### FIXED CODE ###

x=int(input())
print(x**3)
K=int(input())
A,B=map(int,input().split())
a=0    
for i in range(A,B,1):
    if i % K ==0:
       print("OK")
        a+=1
       break 
        
elif a==0:
   print("NG")
   
        

### FIXED CODE ###

K=int(input())
A,B=map(int,input().split())
a=0    
for i in range(A,B+1):
    if i % K ==0:
       a=1
        
if a==0:
  print("NG")
    
else:
  print("OK")
a = int(input())
b=[]
b.append(int(input()))
x = 0
 
if (a==0) :
	print('DENIED')
elif (b.count(0) > 0):
	print('DENIED')
else:
  for i in b:
      if i % a == 0:
          x += 1
  if x == len(b):
      print('APPROVED')
  else:

### FIXED CODE ###

a = int(input())
 
b=list(map(int, input().split())) 
x = 0
c = 0
    
for i in b:
  if ((i % 3 == 0) or (i % 5 == 0)) and (i % 2 == 0):
    x += 1

for t in b:
  if (t%2==0):
    c += 1;

if x == c:
  print('APPROVED')
else :
  print('DENIED')
X = int(input())
if X >= 30:
  print('Yes')
else:
  print('No'9)

### FIXED CODE ###

X = int(input())
if X >= 30:
    print('Yes')
else:
    print('No')
N = input()
K = int(input())

def K1(N):
  le = len(N)
  if le == 1:
    print(int(N))
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    print(0)
  else:
    n = N[1:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    print(0)
  else:
    n1 = N[2:le]
    n2 = N[1:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))
  

### FIXED CODE ###

N = input()
K = int(input())

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N + 1):
    for num in A:
        if i - m[num] >= 0:
            dp[i] = max(dp[i], dp[i - m[num]] + 1)

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)


### FIXED CODE ###

from math import isinf

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

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N + 1):
    for num in A:
        if i - m[num] >= 0:
            dp[i] = max(dp[i], dp[i - m[num]] + 1)

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if matches - m[a] < 0:
            continue
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)
a, b = map(int, raw_input().split())

if a < b:
  print "a < b"
else if a > b:
  print "a > b"
else:
  print "a = b"

### FIXED CODE ###

a, b = map(int, raw_input().split())
 
if a < b:
  print "a < b"
elif a > b:
  print "a > b"
else:
  print "a == b"
n = int(input())
dp = [100000] * 100010
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6],dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9],dp[i]+1)
print(dp[n])

### FIXED CODE ###

n = int(input())
dp = [10**9]*30000000
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9], dp[i]+1)
print(dp[n])
import numpy as np
N, K = map(int, input().split())
H = np.array([int(h) for h in input().split()])


#dp = np.array([0]*(N+1), dtype=np.int32)
dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    if n < K:
        dp[n] = np.amin(dp[np.maximum(n-k, 0)] + np.abs(H[n]-H[np.maximum(n-k, 0)]))
    else:
        dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))


print(dp[N-1])


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
# H = np.array([int(h) for h in input().split()])
H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
k = np.array([i for i in range(1, K+1)])

for n in range(1, N):
    start = max(n-K, 0)
    #if n < K:
    #   dp[n] = np.amin(dp[start] + np.abs(H[n]-H[start]))
    #else:
    #   dp[n] = np.min(dp[n - k] + np.abs(H[n] - H[n - k]))
    dp[n] = np.min(dp[start:n] + np.abs(H[n]-H[start:n]))

print(dp[N-1])
import math;
a, b = map(int, input().split());
def lcm(x, y):
    return (x * y) // math.gcd(x, y);

print(lcm(a, b))

### FIXED CODE ###

import fractions;
a, b = map(int, input().split());
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y);

print(lcm(a, b))
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
for i in range(dp[N]-1):
    b=-1
    for a in A:
        if dp[n-Cost[a]] == k-1:
            b=max(b,a)
        
    k-=1
    n-=Cost[b]
    buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))







### FIXED CODE ###

#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(10**4 + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(2,N+1):
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
for i in range(dp[N]-1):
    b=-1
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] == k-1:
            b=max(b,a)
    k-=1
    n-=Cost[b]
    buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)   
print("".join(map(str,buf)))
from math import log10
n=input()
k=int(input())

#ないときも後で
l=len(n)
ans1=0
if l>k:
    if k==1:
        ans1=l-1
    elif k==2:
        ans1=(l-1)*(l-2)//2
    else:
        ans1=(l-1)*(l-2)*(l-3)//6
ans1*=9**k
ans=0
if l>=k:
    if k==1:
        ans=0
    elif k==2:
        ans=(l-1)
    else:
        ans=(l-1)*(l-2)//2
ans*=(int(n[0])-1)*9**(k-1)

dp=[[0]*3 for _ in range(l-1)]
dp[-1][0]=1
n=list(n)
n.reverse()
for i,c in enumerate(n[:-1]):
    c=int(c)
    dp[i][0]=1
    dp[i][1]=dp[i-1][1]+dp[i-1][0]*c
    dp[i][2]=dp[i-1][2]+dp[i-1][1]*c
ans+=dp[-1][k-1]
print(ans+ans1)

### FIXED CODE ###

n=input()
k=int(input())

n1,n2,n3=int(n[-1]),0,0
a1,a2,a3=9,0,0
for i in n[-2::-1]:
    i=int(i)
    if i!=0:
        n1,n2,n3=i+a1,(i-1)*a1+n1+a2,(i-1)*a2+n2+a3
    a1,a2,a3=9+a1,9*a1+a2,9*a2+a3
print([n1,n2,n3][k-1])
import math

A, B = map(int, input().split())
ans = -1
a1 = math.ceil(A*12.5)
a2 = (A+1)*12.5

a = [i for i in range(a1, int(a2)) if i < a2]

b1 = B*10
b2 = (B+1)*10

b = list(range(b1, b2))

for i in a:
    if i in b:
        ans = i
        break

print(ans)




### FIXED CODE ###

s = input()

ans = 'Yes'

if (s[0] == s[1] == s[2]):
    ans = 'No'

print(ans)
n = int(input())
arr = map(int, input().split())
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
cmp = arr[0]
ans = 0

for i in range(1,len(arr)):
  cmp = max(arr[i],cmp)
  add = cmp - arr[i]
  ans = ans + add

print(ans)
o = list(input())
e = list(input())
ans = []

for i in range(len(o)):
    ans = ans+ [o[i],e[i]]
print(*ans,sep="")

### FIXED CODE ###

o = list(input())
e = list(input())
ans = []

if len(o) != len(e):
    e += [""]

for i in range(len(o)):
    ans += [o[i],e[i]]
print(*ans,sep="")
a,b =map(input())
if a == b:
  print("=")
elif a < b:
  print("<")
else:
  print(">")

### FIXED CODE ###

a,b =input().split()
if a == b:
  print("=")
elif a < b:
  print("<")
else:
  print(">")
import sys
import time
import random
sys.setrecursionlimit(100000000)
N, A, B = map(int, input().split())
sTime = time.time()

P = [-1] * N
Q = [0] * (2**N)
X = [0] * (2**N)
X[0] = 1
X[1] = 1
Y = [1<<i for i in range(N)]
Z = [0]

def calc(k, l, M):
    aa = 0
    bb = 0
    done = [0] * N
    for i in range(M):
        # print("M, i, k,aa,Y=", M, i, k, aa, Y)
        while k & Y[aa] == 0:
            aa += 1
        while l & Y[bb] == 0:
            bb += 1
        P[aa] = bb
        done[bb] = 1
        aa += 1
        bb += 1
    j = 0
    # print(P)
    # print(done)
    for i in range(N):
        if P[i] >= 0:
            continue
        while done[j] == 1:
            j += 1
        P[i] = j
        j += 1

def change(n):
    ret = 0
    for i in range(N):
        if n & (1<<i):
            ret += 1<<P[i]
    return ret

def dc(n):
    return sum(map(int, list(bin(n)[2:])))


def dfs(n, c):
    if time.time() - sTime > 1.75:
        return -1
    for i in range(N):
        m = n ^ Y[i]
        # print(n, i, m, c)
        if c == 2**N - 2 and m == 1:
            X[m] = 1
            Z.append(m)
            return 1
        if X[m] == 0 and m != 1:
            X[m] = 1
            Z.append(m)
            # print(Z)
            r = dfs(m, c+1)
            if r:
                return r
            if r < 0:
                return -1
            X[m] = 0
            Z.pop()
    return 0

if (dc(A) + dc(B)) % 2 == 0:
    print("NO")
else:
    r = dfs(0, 0)
    # print(X, Y, Z)
    if r < 0:
        print(1/0)
    else:
        # print("A", Z[:10], Z[-10:])
        mi = 99999
        while mi > 0:
            # for i in range(3, 2**N-1, 2):
            i = random.randrange(1,2**N-1,2)
            if Z[i-1]^Z[-1] in Y:
                Z = Z[:i] + Z[i:][::-1]
                mi = abs(dc(Z[-1]) - dc(B))
        # print("A", Z[:10], Z[-10:])
        # print("(Z[-1], B, dc(B))", Z[-1], B, dc(B))
        calc(Z[-1], B, dc(B))
        # print("P=", P)
        for i in range(N):
            s = 1<<P[i]
            t = 1<<i
            for j in range(2**N):
                if j & t:
                    Q[j] += s
        Z = [Q[z] for z in Z]
        # print(Z[:10], Z[-10:])
        print("YES")
        print(*Z)
            
        

### FIXED CODE ###

def dc(n):
    return sum(map(int, list(bin(n)[2:])))
def calc(a, b, X):
    if len(X) == 1:
        return [a, b]
    i = 0
    while i not in X or (a & (1<<i)) == (b & (1<<i)):
        i += 1
    j = X[1] if i == X[0] else X[0]
    Y = [x for x in X if x != i]
    return calc(a, a ^ (1<<j), Y) + calc(a ^ (1<<j) ^ (1<<i), b, Y)

N, A, B = map(int, input().split())
if dc(A^B) % 2 == 0:
    print("NO")
else:
    print("YES")
    print(*calc(A, B, list(range(N))))
n,s = (int(i) for i in input().split())
x = list(int(i) for i in input().split())
x = sorted(x)
if n>1:
    dif = []
    for i in range(n-1):
        dif.append(x[i+1]-x[i])

    difs = []
    for i in range(n):
        difs.append(abs(s-x[i]))

    print(res)
    for i in range(res):
        flag = True
        for j in range(n-1):
            if dif[j]%(res-i)!=0:
                flag = False
                break
        if flag:
            res -= i
            break
                
    print(res)
else:
    print(abs(x[0]-s))

### FIXED CODE ###

n,s = (int(i) for i in input().split())
x = list(int(i) for i in input().split())
x = sorted(x)
if n>1:
    dif = []
    for i in range(n-1):
        dif.append(x[i+1]-x[i])

    difs = []
    for i in range(n):
        difs.append(abs(s-x[i]))
    res = min(min(dif),min(difs))
    for i in range(res):
        flag = True
        for j in range(n-1):
            if dif[j]%(res-i)!=0:
                flag = False
                break
        if flag:
            res -= i
            break
                
    print(res)
else:
    print(abs(x[0]-s))
print(x^3)


### FIXED CODE ###

n = int(input())
print(n**3)