题目描述

文字列 $S$ の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から $K$ 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは？ 「文字列 $A$ が文字列 $B$ の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 $A$ と文字列 $B$ に同数含まれるということを指します。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $K$

输出格式

答えを出力せよ。

题目大意

在字符串 $S$ 的全排列中，字典序第 $K$ 小的排列组合是其中的哪种。

aab 2

aba

baba 4

baab

ydxwacbz 40320

zyxwdcba

提示

制約

• $1\ \le\ |S|\ \le\ 8$
• $S$ は英小文字のみからなる
• $S$ の各文字を並べ替えてできる文字列は $K$ 種類以上存在する

Sample Explanation 1

文字列 aab の各文字を並べ替えて作ることが可能な文字列は $\{$ aab, aba, baa $\}$ の $3$ つですが、このうち辞書順で前から $2$ 番目にくるものは aba です。