Lexicographically Smallest String after Rotations

You are given a string s and an integer k. You can perform at most k right rotation operations on s. A right rotation moves the last character of the string to the beginning. Formally, one right rotation transforms a string \( s = s_0s_1\ldots s_{n-2}s_{n-1} \) into \( s' = s_{n-1}s_0s_1\ldots s_{n-2} \).

You need to determine the lexicographically smallest string that can be obtained after performing at most k right rotations. However, if \( k \geq n \) (where \( n \) is the length of s), you are allowed to achieve any permutation of the characters of s (i.e. you can rearrange s arbitrarily). In such a case, the answer is the string sorted in increasing order.

Note: Lexicographical comparison is the same as dictionary order.

Examples:

• For s = "cba" and k = 2, the possible strings are: "cba" (no rotation), "acb" (after 1 rotation), "bac" (after 2 rotations). The answer is "acb".
• For s = "dcba" and k = 4, since \( k \geq n \) (with \( n = 4 \)), the answer is the sorted string "abcd".

inputFormat

The input consists of two lines:

1. The first line contains a non-empty string s.
2. The second line contains an integer k representing the maximum number of rotations.

outputFormat

Output a single line containing the lexicographically smallest string that can be obtained after performing at most k right rotations on s (with arbitrary rearrangement allowed when \( k \geq n \)).

cba
2

acb