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;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n, k;
string s;

string go(string s, int h){
    string ret;
    for(int i = h ; i < n ; i++){
        ret += s[i];
    }
    for(int i = n - 1 ; i >= n - h ; i--){
        ret += s[i];
    }
    return ret;
}
string calc(string s, int k){
    if(k == 0) return s;
    int cnt = 0;
    char c = s.back();
    while(cnt < n && s[n - cnt - 1] == c){
        cnt++;
    }
    if(cnt == n) return s;
    while(k > 1){
        cnt *= 2;
        k--;
        if(cnt >= n){
            return string(n, c);
        }
    }
    while(s.back() == c){
        s.pop_back();
    }
    s += string(cnt, c);
    s = s.substr((int)s.size() - n);
    int r = s.size() - 1;
    while(s[r] == c) r--;
    r++;
    return go(s, r);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> s;
    string ans = s;
    ans = min(s, calc(s, k));
    for(int i = 0 ; i <= n ; i++){
        string cur = go(s, i);
        ans = min(ans, calc(cur, k - 1));
    }
    cout << ans << endl;
}
