Swapping Characters

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

inputFormat

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.

outputFormat

Output

Output the lexicographically smallest string.

Examples

Input

pckoshien 3

Output

ckopshien

Input

pckoshien 10

Output

cekophsin

样例

pckoshien
3

ckopshien