Problem Description

You are undergoing an interview with the DISCO Corporation. The interviewer has given you the following task: "Given a string $S$ consisting only of lowercase English letters, you are allowed to perform exactly $K$ operations by choosing one from three possible operations. Create an amazing string that you think is the best."

The allowed operations are as follows:

1. Delete the $i$-th character of string $S$ where $1 \leq i \leq |S|$.
2. Replace the $i$-th character of string $S$ with another lowercase English letter where $1 \leq i \leq |S|$.
3. Insert a favorite lowercase English letter at the $i$-th position of string $S$ where $1 \leq i \leq |S| + 1$.

You have decided to impress the interviewer by creating the lexicographically smallest possible string that can be formed with $K$ operations.

For a string $X$, $|X|$ denotes the length of string $X$. For two strings $s = s_1s_2s_3...s_n$ and $t = t_1t_2t_3...t_m$, $s < t$ in lexicographical order if either of the following conditions is met:

• There exists an integer $i$ (where $1 \leq i \leq \min(n, m)$) such that for any integer $j$ satisfying $1 \leq j < i$, $s_j = t_j$ and $s_i < t_i$.
• For any integer $i$ (where $1 \leq i \leq \min(n, m$)), $s_i = t_i$ and $n < m$.

Input Format

The input is given from the standard input in the following format:

$S$ $K$

• The first line contains a string $S$ consisting only of lowercase English letters, where $2 \leq |S| \leq 300,000$.
• The second line contains an integer $K$ representing the number of operations you must perform, where $1 \leq K \leq |S| - 1$.

Output Format

Output the lexicographically smallest string that can be formed by performing $K$ operations on $S$. End the output with a newline.

Sample Input and Output

Sample Input #1

abc
1

Sample Output #1

aabc

Sample Input #2

abc
2

Sample Output #2

a

Sample Input #3

acb
1

Sample Output #3

aab

Notes/Hints

Partial Points

This problem has partial scoring:

• Correctly solving the dataset where $2 \leq |S| \leq 10$ and $1 \leq K \leq \min(|S| - 1, 4)$ awards 10 points.
• Correctly solving the dataset where $2 \leq |S| \leq 200$ awards an additional 10 points.
• Correctly solving the dataset where $2 \leq |S| \leq 1,000$ awards an additional 20 points.
• Correctly solving the dataset where $2 \leq |S| \leq 300,000$ awards an additional 60 points, totaling 100 points.

Sample Explanation 1

• The string aabc is the lexicographically smallest string that can be formed with 1 operation by inserting a at the beginning of $S$. This case satisfies the constraints for the first partial score.

Sample Explanation 2

• The string a is the lexicographically smallest string that can be formed with 2 operations by deleting the 2nd and 3rd characters of $S$. This case satisfies the constraints for the first partial score.

Sample Explanation 3

• The string aab is the lexicographically smallest string that can be formed with 1 operation by replacing the 2nd character of $S$. This case satisfies the constraints for the first partial score.

见题面 Input 部分

见题面 Output 部分