ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
Tags: none