Alice and Bob (and string): Double Menace

Time limit2sMemory limit512 MB

Summary

Given string s and k, find the k-th lexicographically smallest substring t of s from which Alice wins the two-sided extension game, or report that fewer than k exist.

Level: Hard9 of 10
Topics: Game theory, String matching, String
Solved: No attempts yet

Problem

Alice and Bob are playing a game. At the start they have a string $s$ and a substring $t$ of $s$ . On each turn, a player adds an arbitrary lowercase letter $c_l$ to the left of $t$ and an arbitrary lowercase letter $c_r$ to the right of $t$ , so that $t$ is still a substring of $s$ . A player who cannot make a valid move loses. Alice moves first.

Before her first move, Alice chooses the initial string $t$ . She wants a choice that guarantees her victory, assuming both players play optimally. To keep Bob from suspecting anything, she picks the $k$ -th lexicographically smallest of all winning initial strings. Help Alice.

Input

The first line contains the string $s$ of lowercase English letters ( $1 \leq |s| \leq 10^5$ ).

The second line contains the integer $k$ ( $1 \leq k \leq 10^{10}$ ).

Output

If there are fewer than $k$ winning initial strings, print "no solution". Otherwise, print the $k$ -th lexicographically smallest winning initial string. If that string is empty, print "-".

Hint

For $s=\mathtt{abac}$ , the winning strings are -, a, b, and ba.

Examples3

Example 1
Input
```
abac
3
```
Expected output
```
b
```
Example 2
Input
```
rndstr
1
```
Expected output
```
-
```
Example 3
Input
```
abc
10
```
Expected output
```
no solution
```