#P1610. Odd-Palindrome

Odd-Palindrome

Odd-Palindrome

Description

定义奇回文串:若字符串 tt 是奇回文串 ,则对于 i[1,t+12]\forall i\in[1,\frac{|t|+1}{2}]ii 为奇数,满足 ti=tti+1t_i=t_{|t|-i+1}

给定一个只包含字符 a,ba,b 的字符串 s ,输出它所有子串中字典序第 kk 小的奇回文串。注意同一子串在字典序排列中出现次数与其在 ss 中出现次数相同

Input Format

第一行输入一个只包含字符 a,ba,b 的字符串 s(1s5000)s(1\le|s|\le5000)

第二行输入一个整数 kk ,含义与上文一致。

Output Format

输出一行包含一个字符串,含义见题目描述。若无解则输出 -1。

Input Example#1

abbabaab
7

Output Example#1

abaa

Input Example#2

aaaaa
10

Output Example#2

aaa

Input Example#3

bbaabb
13

Output Example#3

bbaabb

Data Range

1s50001\le|s|\le5000 .