You are given a string and a number k. You are suggested to generate new strings by swapping any adjacent pair of characters in the string up to k times. Write a program to report the lexicographically smallest string among them.

Input

The input is given in the following format.

s
k

The first line provides a string s. The second line provides the maximum number of swapping operations k (0 ≤ k ≤ 109). The string consists solely of lower-case alphabetical letters and has a length between 1 and 2 × 105.

Output

Output the lexicographically smallest string.

Examples

Input

pckoshien
3

Output

ckopshien

Input

pckoshien
10

Output

cekophsin

见题面

见题面