시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

abac
3

예제 출력 1

b

예제 입력 2

rndstr
1

예제 출력 2

-

예제 입력 3

abc
10

예제 출력 3

no solution

힌트

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