Lexicographical Challenge

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given a string S and an integer K, find the lexicographically smallest string reachable by swapping S_i with S_(i+K) any number of times.

Level: Easy3 of 10
Topics: String, Sorting, Implementation
Solved: No attempts yet

Problem

In the village of Lexicoville, Lily and Ethan received a mysterious letter containing a riddle. The riddle gives an integer $K$ and a string $S$ made only of lowercase letters. At any moment, the villagers may choose an index $i$ and swap the characters $S_i$ and $S_{i+K}$ . Using only this operation, find the lexicographically smallest string that can be obtained.

Input

The first line contains the string $S$ ( $1 \le |S| \le 10^5$ ). The second line contains the integer $K$ ( $1 \le K < |S|$ ).

Output

Output a single line with the lexicographically smallest string that can be obtained.

Examples2

Example 1
Input
```
zaaab
4
```
Expected output
```
baaaz
```
Example 2
Input
```
njoab
2
```
Expected output
```
banjo
```