Alice and Bob are playing a game. Initially they have a string s and its substring t. Each player’s turn consists of adding an arbitrary letter c_{l} to the left of t and an arbitrary letter c_{r} to the right of t in such a way that t is still a substring of s. The player who can’t make a valid move loses.
Alice moves first. Before she makes the first move, she has the right to choose the initial string t. Of course, Alice wants to cheat and will choose such a string t that will guarantee her victory (assuming both players act optimally), but she doesn’t want Bob to suspect anything. Therefore, Alice decided to choose the kth lexicographically smallest string among all possible winning initial strings t. Help Alice!
Input
The first line of input contains string s of lowercase English letters (1 ≤ s ≤ 10^{5}).
The second line contains integer k (1 ≤ k ≤ 10^{10}).
Output
If there are less than k suitable options for the string t, print “no solution
”. Otherwise, print the kth lexicographically smallest one. If the answer is an empty string, print “
” instead.
Samples
input  output 

abac
3
 b

rndstr
1
 

abc
10
 no solution

Notes
Winning strings for s=abac are {
, a
, b
, ba
}.
Problem Author: Oleksandr Kulkov
Problem Source: Petrozavodsk Summer 2018. Moscow IPT Contest