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

from copy import copy

def f(n,cnt):
    if n==0:
        return cnt
    popcnt = bin(n).count('1')
    return f(n%popcnt,cnt+1)

n = int(input())
x = list(input())


for i in range(n):
    y = copy(x)
    if y[i] == '0':
        y[i] = '1'
    else:
        y[i] = '0'

    y = ''.join(y)
    m = int(y,2)
    print(f(m,0))

### FIXED CODE ###

def f(n,cnt):
    if n==0:
        return cnt
    popcnt = bin(n).count('1')
    return f(n%popcnt,cnt+1)

n = int(input())
x = input()

m = int(x,2)
m_cnt = x.count('1')

mp = m%(m_cnt+1)
mm = m%(m_cnt-1) if m_cnt > 1 else 0

for i,s in enumerate(x):
    i = n-1-i
    num = None

    if s == '0':
        mod = m_cnt+1
        num = (mp+pow(2,i,mod))%mod
    elif m_cnt > 1:
        mod = m_cnt-1
        num = (mm-pow(2,i,mod))%mod
    else:
        print(0)
        continue

    print(1+f(num,0))
### BUGGY CODE ###

from math import pow
from itertools import combinations
x = int(input())

def prime_factorize(n):
    a = [1]
    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

def func(a, b):
    return pow(a, 5) - pow(b,5)
    
cands = prime_factorize(x)
ok = False

for i in range(2 ** len(cands)):
    y = 1
    for j in range(len(cands)):        
        if (i >> j) & 1:
            y *= cands[j]
        for a in range(1, y + 1):
            b = a - y
            if func(a, b) == x:
                print(a, b)
                ok = True
                break
        if ok:
            break
    if ok:
        break
        

### FIXED CODE ###

from math import pow
from itertools import combinations
x = int(input())

def func(a, b):
    return pow(a, 5) - pow(b,5)

ok = False
for a in range(-200, 200):
    for b in range(-200, 200):
        if func(a, b) == x:
            print(a, b)
            ok = True
            break
    if ok:
        break
### BUGGY CODE ###

import numpy as np

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

target = sum(a)//2

a = np.array(a)
a = np.concatenate((a, a))
ans = []

for i in range(n):
    num = target
    b = a[i+1:i+n:2]
    num -= np.sum(b)
    ans.append(num*2)

for i in range(n):
    print(ans[i], end=' ')

### FIXED CODE ###

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

target = sum(a)//2

b = a[1:n:2]
a.append(a[0])

ans = []
ans.append((target-sum(b))*2)

for i in range(n-1):
    num = a[i] - ans[i]//2
    ans.append(num*2)

for i in range(n):
    print(ans[i], end=' ')
### BUGGY CODE ###

from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))

import math
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

data=get_sieve_of_eratosthenes(1000000)
def prime_factorization(n):
    arr=[]
    for p in data:
        if p >n:
            break
        if n%p==0:
            arr.append(p)
        
    return arr

isPairwise = True
isSetwise = True
dict=defaultdict(lambda:0)

for i in range(N):
    arr = prime_factorization(A[i])
    for j in range(len(arr)):
        prime=arr[j]
        if prime!=1:
            dict[prime]+=1

for i in dict.values():
    if i==N:
        isPairwise=False
        isSetwise=False
    elif i>1:
        isPairwise=False
    else:
        pass

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
   

### FIXED CODE ###

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

c=[0]*(10**6+5)

isPairwise=True
isSetwise=True
for i in range(N):
    c[A[i]]+=1

for i in range(2,1000005):
    cnt=0
    for j in range(i,1000005,i):
        cnt+=c[j]
    
    if cnt>1:
        isPairwise=False

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

g=0
for i in range(N):
    g=gcd(g,A[i])
if g>1:
    isSetwise=False

if isPairwise:
    print('pairwise coprime')
elif isSetwise:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
d = {}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    if a in d:
        d[a].add(b)
    else:
        d[a] = {b}
    if b in d:
        d[b].add(a)
    else:
        d[b] = {a}
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
visit = set()
while True:
    children = set()
    for parent in parents:
        if parent in visit:
            continue
        visit.add(parent)
        v = counter[parent]
        children |= d[parent]
        for child in d[parent]:
            if child in visit:
                continue
            counter[child] += v
    if len(children) == 0:
        break
    parents = children
print(*counter[1:])

### FIXED CODE ###

N, Q = list(map(int, input().split()))
d = {i: set() for i in range(1, N + 1)}
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
counter = [0] * (N + 1)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    counter[p] += x

parents = {1}
while parents:
    children = set()
    for parent in parents:
        v = counter[parent]
        for child in d[parent]:
            d[child].remove(parent)
            children.add(child)
            counter[child] += v
    parents = children
print(*counter[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(N)]
 
dp = [-1]*(W+1)
dp[0] = 0
for w, v in wv:
    for j in range(W-w, -1, -1):
        if dp[j] >= 0 and dp[j+w] < dp[j]+v:
            dp[j+w] = dp[j] + v
 
print(max(dp))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

def main():
    ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

    N, W = ds_in()

    dp = [[0] * (W+1) for i in range(N+1)]
# dp[index][weight]:=valueとしてdp[n]での最大を求める.
    for i in range(N):
    # pre = values.copy()
        w, v = ds_in()  # [weight, value]
        for j in range(W+1):
            if (j-w>=0):
                dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]
    ans = 0
    for i in range(W+1):
        ans = max(ans, dp[N][i])
    print(ans)
    return 0
main()
### BUGGY CODE ###

from collections import deque
N,M,P=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
C=[0 for i in range(M)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(M):
    A[i],B[i],C[i]=map(int,input().split())
    G[B[i]-1][A[i]-1]=C[i]
    H[A[i]-1][B[i]-1]=C[i]
reached1=[0 for i in range(N)]
q=deque([N-1])
while(len(q)>0):
    r=q.popleft()
    reached1[r]=1
    for p in G[r]:
        if reached1[p]==0:
            q.append(p)
reached2=[0 for i in range(N)]
q=deque([0])
while(len(q)>0):
    r=q.popleft()
    reached2[r]=1
    for p in H[r]:
        if reached2[p]==0:
            q.append(p)
reached=[reached1[i]*reached2[i] for i in range(N)]
vertex_list=[]
vertex_num=[-1 for i in range(N)]
tmp=1
for i in range(N):
    if reached[i]==1:
        vertex_list.append(i+1)
        vertex_num[i]=tmp
        tmp+=1
num_v=len(vertex_list)
edges=[]
for i in range(M):
    if reached[A[i]-1]==1 and reached[B[i]-1]==1:
        edges.append((vertex_num[A[i]-1],vertex_num[B[i]-1],P-C[i]))
inf=10**10
dist=[inf for i in range(num_v)]
dist[0]=0
#print(reached)
#print(edges)
#print(vertex_list)
#print(vertex_num)
#辺の緩和
for i in range(num_v):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
            if i==num_v-1:
                print(-1)
                exit()
print(max(-dist[-1],0))

### FIXED CODE ###

N,M,P=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
C=[0 for i in range(M)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(M):
    A[i],B[i],C[i]=map(int,input().split())
    G[B[i]-1][A[i]-1]=C[i]
    H[A[i]-1][B[i]-1]=C[i]
reached1=[0 for i in range(N)]
q=[N-1]
while(len(q)>0):
    r=q.pop()
    reached1[r]=1
    for p in G[r]:
        if reached1[p]==0:
            q.append(p)
reached2=[0 for i in range(N)]
q=[0]
while(len(q)>0):
    r=q.pop()
    reached2[r]=1
    for p in H[r]:
        if reached2[p]==0:
            q.append(p)
reached=[reached1[i]*reached2[i] for i in range(N)]
vertex_list=[]
vertex_num=[-1 for i in range(N)]
tmp=1
for i in range(N):
    if reached[i]==1:
        vertex_list.append(i+1)
        vertex_num[i]=tmp
        tmp+=1
num_v=len(vertex_list)
edges=[]
for i in range(M):
    if reached[A[i]-1]==1 and reached[B[i]-1]==1:
        edges.append((vertex_num[A[i]-1],vertex_num[B[i]-1],P-C[i]))
inf=10**10
dist=[inf for i in range(num_v)]
dist[0]=0
#print(reached)
#print(edges)
#print(vertex_list)
#print(vertex_num)
#辺の緩和
for i in range(num_v):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
            if i==num_v-1:
                print(-1)
                exit()
print(max(-dist[-1],0))
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,min(i+1,K+1)))
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i))
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
res = 0
for i in range(1,n):
    res += i
print(res)

### FIXED CODE ###

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

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root =[[] for _ in range(N+1)]
    for _ in range(M):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = []
    heapify(q)
    node[1] = 0
    q.append((0,1,-1))

    while q:
        d,v,f = q.pop()
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            q.append((d+1,u,v))

    print('Yes')
    print(*ans[2:],sep='\n')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    root =[[] for _ in range(N+1)]
    for _ in range(M):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    node = [INF] * (N+1)
    ans = [-1] * (N+1)

    q = collections.deque()
    node[1] = 0
    q.append((0,1,-1))

    while q:
        d,v,f = q.popleft()
        node[v] = d
        ans[v] = f
        for u in root[v]:
            if node[u] <= d+1: continue
            node[u] = d+1
            q.append((d+1,u,v))

    print('Yes')
    print(*ans[2:],sep='\n')

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

k,s = list(map(int,input().split()))

count=0
for x in range (k+1):
  for y in range(k+1):
    for z in range(k+1):
      # print(x,y,z,k,s)
      if x+y+z == s:
        count+=1
        
print(count)

### FIXED CODE ###

k,s = list(map(int,input().split()))

count=0
for x in range (k+1):
  for y in range(k+1):
    z = s - x - y
    if z < 0 or z > k:
      continue
    count+=1
        
print(count)
### BUGGY CODE ###

from functools import reduce
n=input()
s=list(map(int,(input().split(" "))))
#s.sort()
ans=reduce(lambda x,y:x*y,s)
if ans > 1e18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n,*l=map(int,open(0).read().split())
a=1
for i in sorted(l):
  a*=i
  if a>10**18: a=-1; break
print(a)
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import random
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))

def warshall_floyd(g):
    d = g
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def slv(N, M, L, ABC, Q, ST):
    g = [[sys.maxsize]*(N) for _ in range(N)]
    for a, b, c in ABC:
        if c > L:
            continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c
    
    d = warshall_floyd(g)
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1
    dd = warshall_floyd(gg)

    for s, t in ST:
        d = dd[s-1][t-1]
        if d != sys.maxsize:
            print(d-1)
        else:
            print(-1)



def main():
    N, M, L = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    Q = read_int()
    ST = [read_int_n() for _ in range(Q)]
    
    (slv(N, M, L, ABC, Q, ST))

    # N = 300
    # M = (N*(N-1))//2
    # L = random.randint(1, 10**9)
    # ABC = []
    # for i in range(1, N+1):
    #     for j in range(i+1, N+1):
    #         ABC.append([i, j, random.randint(1, 10**9)])
    
    # ST = []
    # for i in range(1, N+1):
    #     for j in range(1, N+1):
    #         if i == j:
    #             continue
    #         ST.append([i, j])
    # Q = len(ST)
    # # (slv(N, M, L, ABC, Q, ST))

    # print(N, M, L)
    # for a, b, c in ABC:
    #     print(a, b, c)
    # print(Q)
    # for s, t in ST:
    #     print(s, t)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


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

N = int(input())
A = list(map(int,input().split()))
thres = 10**18
res = A[0]
for i in range(N-1):
   res *= A[i+1]
if res > thres:
    res = -1
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
thres = 10**18
res = A[0]
if 0 in A:
    print(0)
    exit()
for i in range(N-1):
    res *= A[i+1]
    if res > thres:
        res = -1
        break
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [list(map(int, input().split())) for i in range(q)]
ans = []
for n, x, m in query:
    l = [d[i]%m for i in range(k)]
    n -= 1
    zero = l.count(0)
    count = n // k
    zero_total = zero*count
    total = sum(l)*count + x%m
    rem = n % k
    total += sum(l[:rem])
    zero_total += l[:rem].count(0)
    ans.append(n-total//m-zero_total)
print("\n".join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
while A!=0 and C!=0:
    C=C-B
    A=A-D
if C<=0:
    print ('Yes')
else:
    print ('No')

### FIXED CODE ###

A,B,C,D=map(int,input().split())
ta=(C-1)//B+1
tb=(A-1)//D+1
if ta<=tb:
    print ('Yes')
else:
    print ('No')
### BUGGY CODE ###

import sys
import bisect
A,B,Q = [int(n) for n in input().split()]
# N = int(input())
INF = 10 **18
s = [0]*A
t = [0]*B
x = [0]*Q
s = [-INF] + [int(input()) for n in range(A)] + [INF]
t = [-INF] + [int(input()) for n in range(B)] + [INF]
def binary_search(arry, target):
    result = None
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if arry[mid] == target:
            result = mid
            break
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    if result == None:
        result = mid
        if(mid+1 < len(arry)):
            result = mid+1 if (abs(arry[mid+1] - target) < abs(arry[mid] - target)) else result
        if(mid-1 >= 0):
            result = mid-1 if (abs(arry[result] - target) > abs(arry[mid-1] - target)) else result
        return result
    else:
        return result+1

for q in range(Q):
    x = int(input())
    mostntera = binary_search(s,x)
    # print(mostntera)
    tera0 = s[mostntera]
    tera1 = s[mostntera-1] if x-tera0<0 else s[mostntera+1]
    # print(tera0,tera1)
    mostnzin = binary_search(t,x)
    zin0 = t[mostnzin]
    zin1 = t[mostnzin-1] if x-zin0<0 else t[mostnzin+1]
    # print(zin0,zin1)
    ans = INF
    for a in [tera0, tera1]:
        for b in [zin0,zin1]:
            d1,d2 = abs(x-a) +abs(a-b), abs(x-b) + abs(a-b)
            ans = min(ans,d1,d2)
    print(ans)


### FIXED CODE ###

import sys
import bisect
A,B,Q = [int(n) for n in input().split()]
# N = int(input())
INF = 10 **18
s = [0]*A
t = [0]*B
s = [-INF] + [int(input()) for n in range(A)] + [INF]
t = [-INF] + [int(input()) for n in range(B)] + [INF]

for i in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

s=input()
k=int(input())

li=set()

for i in range(len(s)):
  for j in range(i,len(s)):
    li.add(s[i:j+1])

li=list(li)
li.sort()

print(li[k-1])

### FIXED CODE ###

s=input()
k=int(input())

li=set()

for p in range(5):
  for i in range(len(s)-p):
    li.add(s[i:i+1+p])
li=list(li)
li.sort()
#print(li)
print(li[k-1])
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, Counter

    n = int(readline())
    mat = [list(map(int, readline().split())) for _ in range(n)]

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        for j in range(n - 2):
            y = mat[x - 1][j]
            z = mat[x - 1][j + 1]
            uf, us = min(x, y), max(x, y)
            vf, vs = min(x, z), max(x, z)
            edge[(uf, us)].append((vf, vs))
            count[(uf, us)] += 0
            count[(vf, vs)] += 1

    ans = 0
    while count:
        ans += 1
        today = [key for key, val in count.items() if val == 0]
        if not today:
            print(-1)
            return

        for cur_match in today:
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
            del count[cur_match]

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_id(x, y):
        return min(x, y) * 10007 + max(x, y)

    from collections import defaultdict, Counter, deque
    from copy import copy

    n = int(readline())

    edge = defaultdict(list)
    count = Counter()

    for x in range(1, n + 1):
        a = list(map(int, readline().split()))
        count[calc_id(x, a[0])] += 0
        for j in range(n - 2):
            y = a[j]
            z = a[j + 1]
            u_id = calc_id(x, y)
            v_id = calc_id(x, z)
            edge[u_id].append(v_id)
            count[v_id] += 1

    ans = 0
    rem = n * (n - 1) // 2
    que = deque()
    for key, val in count.items():
        if val == 0:
            que.append(key)
    que_tomorrow = deque()

    while rem:
        ans += 1
        if not que:
            print(-1)
            return
        while que:
            cur_match = que.popleft()
            for nx_match in edge[cur_match]:
                count[nx_match] -= 1
                if count[nx_match] == 0:
                    que_tomorrow.append(nx_match)
            rem -= 1
        que = copy(que_tomorrow)
        que_tomorrow.clear()

    print(ans)


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

import numpy as np

H, N = map(int, input().split())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
dp_max = 10000000000
dp = np.full(H+1, dp_max, dtype=int)
dp[0] = 0

for i in range(H+1):
  if dp[i] == dp_max:
    continue

  for j in range(N):
    ni = min(H, i + A[j])

    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])

### FIXED CODE ###

#import numpy as np
 
H, N = map(int, input().split())
A, B = [], []
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
dp_max = 10000000000
dp = [dp_max for i in range(H+1)]
#dp = np.full(H+1, dp_max, dtype=int)
dp[0] = 0
 
for i in range(H+1):
  if dp[i] == dp_max:
    continue
 
  for j in range(N):
    ni = min(H, i + A[j])
 
    dp[ni] = min(dp[ni], dp[i] + B[j])
print(dp[H])
### BUGGY CODE ###

s = input()
k = int(input())

alphabet = "abcdefghijklmnopqrstuvwxyz"
candidates = []

for i in range(len(alphabet)):
  key = alphabet[i]
  count = s.count(key)
  if count > 0:
    index = 0
    for j in range(count):
      index = s.find(key, index)
      for i in range(index, len(s) + 1):
        if not s[index:i] in candidates and len(s[index:i]) > 0 and len(s[index:i]) <= k:
          candidates += [s[index:i]]
      index += 1
  if len(candidates) >= k:
    break

candidates.sort()
print(candidates[k - 1])

### FIXED CODE ###

s = input()
k = int(input())

#alphabet = "abcdefghijklmnopqrstuvwxyz"
candidates = []

for i in range(len(s)):
  for j in range(i + 1, len(s) + 1):
    if not s[i:j] in candidates:
      candidates += [s[i:j]]
    if len(s[i:j]) >= k:
      break

candidates.sort()
print(candidates[k - 1])