18966번 - Alice and Bob (and string): Double Menace 다국어

문제

From the creators of "Alice and Bob (and string)" and "Alice and Bob (and string) Strikes Back"!

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ドル \leq |s| \leq 10^5$).

The second line contains integer $k$ (1ドル \leq k \leq 10^{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=\mathtt{abac}$ are -, a, b, ba.