C - One More aab aba baa Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

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

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

制約

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

入力

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

S K

出力

答えを出力せよ。

入力例 1

aab 2

出力例 1

aba

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

入力例 2

baba 4

出力例 2

baab

入力例 3

ydxwacbz 40320

出力例 3

zyxwdcba

Score : 300 points

Problem Statement

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

What is a permutation of a string?A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.

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.

Sample Input 1

aab 2

Sample Output 1

aba

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

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba