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

def main():
  n=int(input())
  p=[float(i) for i in input().split()]
  
  dp=[[0]*(n+1) for i in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    dp[i+1][0]=dp[i][0]*(1-p[i])
    for j in range(i+1):
      dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i])
  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()
        

### FIXED CODE ###

def main():
  n=int(input())
  p=[float(i) for i in input().split()]
  
  dp=[[0]*(n+1) for i in range(n+1)]
  dp[0][0]=1
  for i in range(n):
    dp[i+1][0]=dp[i][0]*(1-p[i])
    for j in range(i+1):
      dp[i+1][j+1]=dp[i][j]*p[i]+dp[i][j+1]*(1-p[i])
  print(sum(dp[n][(n+1)//2:]))
      
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

### FIXED CODE ###

n,k,q=map(int,input().split())
a= []
for _ in range(q):
    a.append(int(input()))
ans=[0]*n
for i in range(q):
    ans[a[i]-1]=ans[a[i]-1]+1
for i in range(n):
    if ans[i]>q-k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n , m = map(int,input().split())
price_li = list(map(int,input().split()))
np_li = np.array(price_li) 
for i in range(m):
    np_li[np_li.argmax()] = np.amax(np_li) // 2
print(sum(np_li))

### FIXED CODE ###

import heapq
n, m = map(int,input().split())
price_li = [-int(i) for i in input().split()]
heapq.heapify(price_li)
for _ in range(m):
    j = -heapq.heappop(price_li)
    j //= 2
    heapq.heappush(price_li,-j)
print(-sum(price_li))
### BUGGY CODE ###

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

idx = 1
idx_count = 0
idx_set = []
for i in range(N):
  if idx != B[i]:
    tmp1 = int(idx_count*(idx_count-1)/2)		# 同一の整数を持つボールの組合せ数
    tmp2 = int((idx_count-1)*(idx_count-2)/2)	# 同一の整数を持つボールを1つ除いたときの組合せ数
    idx_set.append([idx, tmp1, tmp2])
    idx_count = 0
    idx = B[i]
  idx_count+=1
if idx_count != 0:
  tmp1 = int(idx_count*(idx_count-1)/2)			# 同一の整数を持つボールの組合せ数
  tmp2 = int((idx_count-1)*(idx_count-2)/2)		# 同一の整数を持つボールを1つ除いたときの組合せ数
  idx_set.append([idx, tmp1, tmp2])

idx_sum_set = []
all_c = 0
for i in range(len(idx_set)):
  all_c += idx_set[i][1]
for i in range(len(idx_set)):
  for j in range(len(idx_set)):
    if i == j:
      tmp = all_c-idx_set[j][1]+idx_set[j][2]
      idx_sum_set.append([idx_set[i][0], tmp])
"""
for i in range(len(idx_set)):
  tmp = 0
  for j in range(len(idx_set)):
    if i == j:	tmp += idx_set[j][2]
    else:		tmp += idx_set[j][1]
  idx_sum_set.append([idx_set[i][0],tmp])
"""

for i in range(N):
  j = int(len(idx_sum_set)/2)
  while 1:
    if A[i] == idx_sum_set[j][0]:
      print(idx_sum_set[j][1])
      break
    elif A[i] > idx_sum_set[j][0]:
      j = j + int((len(idx_sum_set)-j)/2)
    elif A[i] < idx_sum_set[j][0]:
      j = int(j/2)
"""
for i in range(N):
  for j in range(len(idx_sum_set)):
    if A[i] == idx_sum_set[j][0]:
      print(idx_sum_set[j][1])
"""



### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.zeros(N+1)

for i in range(N):
  B[A[i]]+=1
#print(B)

all_c = 0
for i in range(1,N+1):
  all_c += int(B[i]*(B[i]-1)/2)			# 同一の整数を持つボールの組合せ数
for i in range(N):
  if B[A[i]] != 0:
    print(int(all_c-(B[A[i]]-1)))
### BUGGY CODE ###

N = int(input())
p = [2]
for i in range(3, int(10**(7/2))):
    for prime in p:
        if i % prime == 0:
            break
        if prime == p[-1] or prime**2 > i:
            p.append(i)
            break      
SUM = 1
for K in range(2, N+1):
    d_K = K
    for prime in p:
        if K == 1:
            break
        count_p = 1
        while K % prime == 0:
            count_p += 1
            K = K // prime
        d_K *= count_p
    SUM += d_K
print(SUM)

### FIXED CODE ###

N = int(input())
SUM = 0
for i in range(1, N+1):
    SUM += (i*(N//i)*((N//i)+1))//2
print(SUM)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    if R // 2019 != L // 2019:
        ans = 0
    else:
        # ansLi = L % 2019
        # ansLj = (L+1) % 2019
        # ansL = ansLi * ansLj

        # ansRi = R % 2019
        # ansRj = (R-1) % 2019
        # ansR = ansRi * ansRj
        ansL = L*(L+1) % 2019
        ansR = R*(R-1) % 2019

        ans = min(ansL, ansR)

    return int(ans)

# print(main())

def search_all():
    if R // 2019 != L // 2019:
        ans = 0
    ans = float("inf")
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(i*j % 2019, ans)
            if ans == 0:
                break
    return ans

print(search_all())

### FIXED CODE ###

import sys

input = sys.stdin.readline

L, R = map(int, input().split())

def main():
    if R // 2019 != L // 2019:
        ans = 0
    else:
        # ansLi = L % 2019
        # ansLj = (L+1) % 2019
        # ansL = ansLi * ansLj

        # ansRi = R % 2019
        # ansRj = (R-1) % 2019
        # ansR = ansRi * ansRj
        ansL = L*(L+1) % 2019
        ansR = R*(R-1) % 2019

        ans = min(ansL, ansR)

    return int(ans)

# print(main())

def search_all():
    if R // 2019 != L // 2019:
        return 0
    ans = float("inf")
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(i*j % 2019, ans)
            if ans == 0:
                break
    return ans

print(search_all())
### BUGGY CODE ###

import itertools
import math
x = int(input())

remain = x % 100
quotient = math.floor(x/100)

items = [100, 101, 102, 103, 104, 105]
n = 6

for moneys in itertools.product(items, repeat=quotient):
    if sum(moneys) == x:
        print(1)
        exit()
print(0)


### FIXED CODE ###

import itertools
import math
x = int(input())

remain = x % 100
quotient = math.floor(x/100)

items = [100, 101, 102, 103, 104, 105]
n = 6

for moneys in itertools.combinations_with_replacement(items, quotient):
    if sum(moneys) == x:
        print(1)
        exit()
print(0)
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
# def GCD(a: int, b: int) -> int:
#     return a if b == 0 else GCD(b, a % b)


class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        # idx番目の要素をxに更新する
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        # [a, b)の最小値を求める
        if r <= a or b <= l:
            # [a, b)が[l, r)と交差しない
            return self.ele_id

        if a <= l and r <= b:
            # [a, b)が[l, r)を完全に含む
            return self.data[k]
        else:
            # [a, b)と[l, r)は一部被る
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = tuple(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

l = [0]
r = [0]
for i in range(n):
    l.append(GCD(l[i], a[i]))
    r.append(GCD(r[i], a[n-1 - i]))
r = r[::-1]

ans = 1
for i in range(n):
    ans = max(ans, GCD(l[i], r[i+1]))

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
  l = [0 for i in range(n)]
  r = [0 for i in range(n)]
  for i in range(n):
    l[max(0, i-a[i])] += 1
    r[min(i+a[i], n-1)] += 1
    
  lighted = 0
  for i in range(n):
    lighted += l[i]
    a[i] = lighted
    lighted -= r[i]
  if len(set(a)) == 1 and a[0] == n:
    break
print(' '.join(list(map(str, a))))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
  l = [0 for i in range(n)]
  r = [0 for i in range(n)]
  for i in range(n):
    l[max(0, i-a[i])] += 1
    r[min(i+a[i], n-1)] += 1
    
  lighted = 0
  for i in range(n):
    lighted += l[i]
    a[i] = lighted
    lighted -= r[i]
  if len(set(a)) == 1 and a[0] == n:
    break
print(' '.join(list(map(str, a))))
### BUGGY CODE ###

import math
import sys

M=list(map(int,input().split()))
x=[]
def cf(x1,x2):
  cf=[]
  for i in range(1,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf
    
def searchPrimeNum(N):
    max = int(math.sqrt(N))
    searchList = [i for i in range(2,N+1)]
    primeNum = []
    while searchList[0] <= max:
        primeNum.append(searchList[0])
        tmp = searchList[0]
        searchList = [i for i in searchList if i % tmp != 0]
    primeNum.extend(searchList)
    return primeNum
P=[]
x=cf(M[0],M[1])
if M[0]!=1 and M[1]!=1: 
  P=searchPrimeNum(min(M[0],M[1]))
P.append(1)
cnt=0

for i in x:
  if i in P:
    cnt+=1
    
print(cnt)

### FIXED CODE ###

import math
import sys

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


def prime(i):
  k=[]
  num=i
  j=2
  while j*j<=num:
    if i%j==0:
      i//=j
      k.append(j)
    else:
      j+=1
  if i!=1:
    k.append(i)
  k.append(1)
  return k

a=set(prime(M[0]))
b=set(prime(M[1]))
print(len(list(a&b)))
### BUGGY CODE ###

import numpy

tmp=input()
list=input().split(" ")
#list = map((lambda e: int(e)), list)
#array=numpy.zeros(len(list),dtype=">i4")
#for i in range(len(list)):
#  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  list = [s.replace(b[0],b[1]) for s in list]
  list2=map((lambda e: int(e)),list)
  print(sum(list2))
  #if int(b[0]) in array:
  #  pos=numpy.where(array==int(b[0]))[0]
  #  for j in pos:
  #    array[j]=int(b[1])
  #  sum=numpy.sum(array)
  #  print(sum)
  #else:
  #  sum=numpy.sum(array)
  #  print(sum)
  

### FIXED CODE ###

import numpy

tmp=input()
list=input().split(" ")
list=[int(x) for x in list]
array=numpy.array(list,dtype=">i4")
sum=numpy.sum(array)
all=numpy.zeros(100001,dtype=">i4")
for i in array:
  all[i]+=1
#for i in range(len(list)):
#  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  b0=int(b[0])
  b1=int(b[1])
  diff=all[b0]*(b1-b0)
  sum+=diff
  all[b1]+=all[b0]
  all[b0]=0
  print(sum)
### BUGGY CODE ###

import sys
N = int(input())

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


MAX = max(A)

if A.count(MAX) == N:
  for _ in range(N):
    print(MAX)

  
else:

  two = sorted(set(A))[-2]
  for i in range(N):
    if A[i] == MAX and A.count(MAX) == 1:
      print(two)
    else:
      print(MAX)

### FIXED CODE ###

N = int(input())

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


MAX = max(A)

if A.count(MAX) != 1:
  for _ in range(N):
    print(MAX)

  
else:

  two = sorted(set(A))[-2]
  for i in range(N):
    if A[i] == MAX :
      print(two)
    else:
      print(MAX)
### BUGGY CODE ###

import math

N, K = [int(x) for x in input().split()]
As = sorted([int(x) for x in input().split()])
Fs = sorted([int(x) for x in input().split()], reverse=True)

def in_n_sec(n):
  #print(n)
  #print(Fs)
  max_allowed = [int(n/F) for F in Fs]
  #print(max_allowed)
  #print(As)
  #print([max(0, a-ma) for a, ma in zip(As, max_allowed)])
  total_training = sum(max(0, a-ma) for a, ma in zip(As, max_allowed))
  #print(total_training)
  return total_training <= K
  
current_worst_confirmed = 10**12
current_best_possible = 0
while current_worst_confirmed > current_best_possible:
  #print(current_worst_confirmed, current_best_possible)
  to_try = (current_worst_confirmed + current_best_possible ) // 2
  if in_n_sec(to_try):
    current_worst_confirmed = to_try
  else:
    current_best_possible = to_try + 1
print(current_worst_confirmed)
    
  


### FIXED CODE ###

import math

N, K = [int(x) for x in input().split()]
As = sorted([int(x) for x in input().split()])
Fs = sorted([int(x) for x in input().split()], reverse=True)

def in_n_sec(n):
  total_training = sum(max(0, a-int(n/f)) for a, f in zip(As, Fs))
  return total_training <= K
  
current_worst_confirmed = 10**12
current_best_possible = 0
while current_worst_confirmed > current_best_possible:
  to_try = (current_worst_confirmed + current_best_possible ) // 2
  if in_n_sec(to_try):
    current_worst_confirmed = to_try
  else:
    current_best_possible = to_try + 1
print(current_worst_confirmed)
### BUGGY CODE ###

mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 0
while A != [0 for i in range(N)]:
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += (m * n) * (2 ** j)
  S %= mod
  j += 1
print(S)

### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

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

mod = 10**9+7
dp = [0] * (n+1)
dp[0] = 1

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

### FIXED CODE ###

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

N = int(input())

def calculate_n(x, y, z):
  n = x**2 + y**2 + z**2 + x*y + y*z + z*x
  return n
l = []
for x in range(1, N):
  for y in range(1, N):
    for z in range(1, N):
      n = calculate_n(x,y,z)
      if n > N:
      	break
      else:
        l.append(n)

numbers = sorted(set(l))
counts = [l.count(x) for x in numbers]
d = dict(zip(numbers, counts))

for i in range(1, N+1):
  if i in d:
  	print(d[i])
  else:
    print(0)

### FIXED CODE ###

N = int(input())
 
def calculate_n(x, y, z):
  n = x**2 + y**2 + z**2 + x*y + y*z + z*x
  return n
l = []
for x in range(1, N):
  for y in range(1, N):
    for z in range(1, N):
      n = calculate_n(x,y,z)
      if n > N:
        break
      else:
        l.append(n)
    if calculate_n(x, y+1, 1) > N:
      break
  if calculate_n(x+1, 1, 1) > N:
    break

import collections
c = collections.Counter(l)
for i in range(1, N+1):
  if i in c:
    print(c[i])
  else:
    print(0)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    #print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    #print(B)
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)
### BUGGY CODE ###

from collections import Counter
[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
gyoretu=[]
for i in range(N):
    row=[]
    for j in range(N):
        if i == j:
            row.append(0)
        elif abs(i - j) == 1 or i == X and j == Y or i == Y and j == X:
            row.append(1)
        else:
            row.append(2000)
    gyoretu.append(row)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if gyoretu[i][j]> gyoretu[i][k] + gyoretu[k][j]:
                gyoretu[i][j] =gyoretu[i][k] + gyoretu[k][j]
array=[]
for i in range(N):
        array+=gyoretu[i][i:]
c=Counter(array)
for i in range(1, N):
    print(c[i])

### FIXED CODE ###

[N, X, Y] = [int(item) for item in input().split()]
X -= 1
Y -= 1
count=[0 for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        count[min(abs(i-j),abs(i-X)+1+abs(Y-j),abs(i-Y)+1+abs(X-j))]+=1
#print(array)


for i in range(1,N):
        print(count[i])

#print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 1

for i in range(n):
    ans *= a[i]

if ans > 10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = input().split()

ans = 1

for i in range(n):
    ans *= int(a[i])
    if ans > 10**18:
        if "0" in a:
            print(0)
            exit()
        else:
            print(-1)
            exit()

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

N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(a) for a in input().split()])

Temp = [0 for i in range(N)]
num = 0
while num <= N-2:
    if S[num] == "A" and S[num+1] == "C":
        Temp[num] = 1
        Temp[num+1] = 2
    num += 1

for j in range(Q):
    Temp2 = Temp[L[j][0]-1:L[j][1]]
    c = sum(Temp2)
    if c%3 == 0:
        if Temp2[0] != 2:
            print(int(c/3))
        else:
            print(int(c/3-1))
    elif c%3 == 1:
        print(int((c-1)/3))
    else:
        print(int((c-2)/3))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
L = []
for i in range(Q):
    L.append([int(x) for x in input().split()])
    
ac_list = [0 for i in range(N)]
ac_num = 0
for i in range(1, N):
    pre = S[i-1]
    ac_list[i] = ac_list[i-1]
    if pre == "A" and S[i] == "C":
        ac_num += 1
        ac_list[i] = ac_num

for i in range(Q):
    ans = ac_list[L[i][1]-1] - ac_list[L[i][0]-1]
    print(ans)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		rem = lengths[j + 1:]
		res += bisect_left(rem, l1 + l2)

print(res)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
lengths = sorted(map(int, input().split()))

res = 0
for i in range(n):
	l1 = lengths[i]
	for j in range(i + 1, n - 1):
		l2 = lengths[j]
		res += bisect_left(lengths, l1 + l2, j + 1) - j - 1

print(res)
### BUGGY CODE ###

import math
import numpy as np

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

A = np.array([[1, 2],
           [2, 1]])

b = np.array([x, y])

N = np.linalg.solve(A, b)


if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
  
  k = math.factorial(N[0]+N[1])/(math.factorial(N[0])*math.factorial(N[1]))

  print(int(k%1000000007))

else:
  print(0)


### FIXED CODE ###

import math
import numpy as np

def cmb(n, r, mod):
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )

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

if (x+y) % 3 == 0:

  A = np.array([[1, 2],
                [2, 1]])

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
        
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))

  else:
      print(0)

else:
  print(0)
### BUGGY CODE ###

s = input()
k = int(input())
substrings = []
index = []
for ss in sorted(list(set(s))):
  index_list = [n for n, v in enumerate(s) if v == ss]
  index.append(index_list)
  if len(s)-min(index_list) >=k:
    break

for ind in index:
  for i in ind:##初期位置
    for j in range(1,len(s)-i+1):##長さ
      substrings.append(s[i:i+j])
  if len(set(substrings)) >= k:
    break

print(sorted(list(set(substrings)))[k-1])

### FIXED CODE ###

s = input()
k = int(input())
substrings = []
index = []
for ss in sorted(list(set(s))):
  index_list = [n for n, v in enumerate(s) if v == ss]
  for i in index_list:##初期位置
    for j in range(1,min(k+1,len(s)-i+1)):##長さ
      substrings.append(s[i:i+j])
  if len(set(substrings)) >= k:
    break
print(sorted(list(set(substrings)))[k-1])
### BUGGY CODE ###

import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    cost = {0: [], 1: [], 2: []}
    ans = INF
    for c in range(1, C + 1):
        cost0 = 0
        cost1 = 0
        cost2 = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    cost0 += D[grid[i][j]][c]
                elif (i + j) % 3 == 1:
                    cost1 += D[grid[i][j]][c]
                elif (i + j) % 3 == 2:
                    cost2 += D[grid[i][j]][c]

        cost[0].append((c, cost0))
        cost[1].append((c, cost1))
        cost[2].append((c, cost2))

    cost[0].sort(key=lambda x: x[1])
    cost[1].sort(key=lambda x: x[1])
    cost[2].sort(key=lambda x: x[1])

    ans = INF
    for c0, cost0 in cost[0][:3]:
        for c1, cost1 in cost[1][:3]:
            for c2, cost2 in cost[2][:3]:
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                tmp = cost0 + cost1 + cost2
                if tmp < ans:
                    ans = tmp

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    D = [[0] * (C + 1)]
    for _ in range(C):
        d = [0] + list(map(int, input().split()))
        D.append(d)

    grid = [[0] * (N + 1)]
    for _ in range(N):
        g = [0] + list(map(int, input().split()))
        grid.append(g)

    cost = {0: [], 1: [], 2: []}
    ans = INF
    for c in range(1, C + 1):
        cost0 = 0
        cost1 = 0
        cost2 = 0
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                if (i + j) % 3 == 0:
                    cost0 += D[grid[i][j]][c]
                elif (i + j) % 3 == 1:
                    cost1 += D[grid[i][j]][c]
                elif (i + j) % 3 == 2:
                    cost2 += D[grid[i][j]][c]

        cost[0].append((c, cost0))
        cost[1].append((c, cost1))
        cost[2].append((c, cost2))

    cost[0].sort(key=lambda x: x[1])
    cost[1].sort(key=lambda x: x[1])
    cost[2].sort(key=lambda x: x[1])

    ans = INF
    for c0, cost0 in cost[0][:3]:
        for c1, cost1 in cost[1][:3]:
            for c2, cost2 in cost[2][:3]:
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                tmp = cost0 + cost1 + cost2
                if tmp < ans:
                    ans = tmp

    print(ans)


if __name__ == "__main__":
    main()