Swapping Characters

Time Limit : 2 sec, Memory Limit : 262144 KB

文字列スワップ

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

Input

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

s
k

1行目にユーザ名の文字列 s が与えられる。2行目に交換回数の上限 k (0 ≤ k ≤ 109) が与えられる。文字列は、英小文字だけから成る、長さが 1 以上 2 × 105 以下の文字列である。

Output

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

Sample Input 1

pckoshien
3

Sample Output 1

ckopshien

Sample Input 2

pckoshien
10

Sample Output 2

cekophsin

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-9-9
http://web-ext.u-aizu.ac.jp/pc-concours/