ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1897. Alice and Bob and a string

Time limit: 1.0 second
Memory limit: 256 MB
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 cl to the left of t and an arbitrary letter cr 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!

Input

The first line of input contains string s of lowercase English letters (1 ≤ |s| ≤ 105).
The second line contains integer k (1 ≤ k ≤ 1010).

Output

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.

Samples

inputoutput
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