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 k-th lexicographically smallest string among all possible winning initial strings t. Help Alice!

The first line of input contains string s of lowercase English letters (1 ≤ |s| ≤ 10⁵).

The second line contains integer k (1 ≤ k ≤ 10¹⁰).

If there are less than k suitable options for the string t, print “no solution”. Otherwise, print the k-th lexicographically smallest one. If the answer is an empty string, print “-” instead.

Winning strings for s=abac are {-, a, b, ba}.