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;

string reverse_string(string p)
{
    int i, sz = p.size();
    for (i = 0; i < sz / 2; i ++)
        swap(p[i], p[sz - i - 1]);
    return p;
}
int main()
{
    int n, k, i = 1;
    string s;
    cin >> n >> k >> s;

    string p = s;
    while(i < k)
    {
        string rev = reverse_string(p);
        string kk = p + rev;
        string opt = rev;
        int j, sz = n * 2;
        for (j = 0; j <= sz - n; j ++)
        {
            string d = kk.substr(j, n);
            string rev_d = reverse_string(d);
            if (rev_d < reverse_string(opt))opt = d;
        }
        if (opt == p)
        {
            cout << opt << endl;
            return 0;
        }
        p = opt;
        i ++;
    }
    string r = p + reverse_string(p);
    string ans = p;
    int sz = n * 2;
    for (i = 0; i <= sz / 2; i ++)
    {
        string d = r.substr(i, n);
        if (d < ans)
            ans = d;
    }
    cout << ans << endl;
    return 0;
}

