Takahashi has a string S of length N consisting of lowercase English letters. On this string, he will perform the following operation K times:

* Let T be the string obtained by reversing S, and U be the string obtained by concatenating S and T in this order.
* Let S' be some contiguous substring of U with length N, and replace S with S'.



Among the strings that can be the string S after the K operations, find the lexicographically smallest possible one.

Constraints

* 1 \leq N \leq 5000
* 1 \leq K \leq 10^9
* |S|=N
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N K
S


Output

Print the lexicographically smallest possible string that can be the string S after the K operations.

Examples

Input

5 1
bacba


Output

aabca


Input

10 2
bbaabbbaab


Output

aaaabbaabb
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    char c = *min_element(s.begin(), s.end());
    string t = s;
    reverse(t.begin(), t.end());
    string u = s + t;
    int m = 1;
    while (k > 1 && m < n) {
        m = min(n, 2 * m);
        --k;
    }
    string ans;
    for (int i = 0; i <= n; ++i) {
        s = u.substr(i, n);
        if (s.back() != c)
            continue;
        int len = 0;
        while (len < n && s[n - len - 1] == c)
            ++len;
        int f = min(n, len * m);
        s = s.substr(f - len, n - f);
        while (s.length() < n)
            s += c;
        reverse(s.begin(), s.end());
        if (ans.empty() || ans > s)
            ans = s;
    }
    cout << ans << endl;
    return 0;
}