Snowman

Do you wanna build a snowman? Of course you do! And you finally have enough snow on the walk in front of your house. But the snow on different sections of the walkway has different quality: on some sections the snow is good, white, and sticky, so call such sections class a sections, sections with a bit worse quality have class b, even worse quality is class c, and so on.

To build a base for a snowman, you roll a snowball forward or backward from one track section to another. There is enough snow, so you can return to the same section as many times as you want. You want to build a snowman out of the best snow, and the closer to the centre of the snowball, the more important the quality of the snow is for the future snowman, so at the beginning of the building process you should choose the best sections. For example, if you roll a snowball starting on a section with class c, then on a section with class a, and then on a section with class b (cab), it would not be as solid as the bab ball, and the aca snowball would be even better.

The classes of the track sections are written in the string $s$. To make the first ball, you need to roll it through track sections $k$ times. You can start rolling a ball for the snowman at any section of the track. What sequence of sections should be used to get the most solid ball?

The first line contains the string $s$ of lowercase letters: the classes of the track sections. The number of sections is not less than 2 and not greater than 100.

The second line contains one integer $k$ ($1 \le k \le 10^4$): the number of sections for the snowball.

Print the sequence of letters without spaces: the section classes in the order you will roll the ball.