0963 - 人気のユーザ名

お知らせ

8/27 11:35 問題の制約を修正しました。

問題

最近ワカマツ国で流行の「グチッター」は、「ぼやき」を投稿するサービスです。
閲覧数を稼ぎたいまさるくんは、どうすれば人気が出るかを調べてみました。
どうやらユーザ名の文字列が辞書順で前にある人ほど人気があるようです。
まさるくんはすでにユーザ名を登録していますが、一定の回数までであれば、登録したユーザ名の隣接する２文字の順番を交換することができるようです。

課題

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

入力

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

s
k

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

出力

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

入出力例

入力例1

pckoshien
3

出力例1

ckopshien

入力例2

pckoshien
10

出力例2

cekophsin