Score : $300$ points

Problem Statement

Find the $K$-th lexicographically smallest string among the strings that are permutations of a string $S$.

Constraints

• $1 \le |S| \le 8$
• $S$ consists of lowercase English letters.
• There are at least $K$ distinct strings that are permutations of $S$.

Input

Input is given from Standard Input in the following format:

$S$ $K$

Output

Print the answer.

aab 2

aba

There are three permutations of a string aab: $\{$ aab, aba, baa $\}$. The $2$-nd lexicographically smallest of them is aba.

baba 4

baab

ydxwacbz 40320

zyxwdcba