文字列スワップ

文字列と交換回数の上限が与えられたとき、与えられた上限以内で文字列内の隣接する２文字の順番を交換してできる新しい文字列の中から、辞書順で最小になるものを報告するプログラムを作成せよ。

Input

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

s
k

１行目に文字列 s が与えられる。２行目に交換回数の上限 k (0 ≤ k ≤ 10⁹) が与えられる。文字列は、英小文字だけから成る、長さが 1 以上 2 × 10⁵ 以下の文字列である。

Output

辞書順で最小の文字列を１行に出力する。

Sample Input 1

pckoshien
3

Sample Output 1

ckopshien

Sample Input 2

pckoshien
10

Sample Output 2

cekophsin

---