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<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=int(1e4+5);
int n,k;
char Max,Min,Ans[MAXN],s[MAXN];
void Check(char *s,int k) {
    char t[MAXN];
    int nw=n,len=0;
    while(nw>=1&&s[nw]==Min)
        nw--,len++;
    while(k!=0&&len<n)
        len*=2,k--;
    if(len>=n) {
        for(int i=1;i<=n;i++)
            Ans[i]=Min;
        printf("%s\n",Ans+1);
        exit(0);
    }
    for(int i=1;i<=len;i++)
        t[i]=Min;
    for(int i=len+1;i<=n;i++)
        t[i]=s[nw--];
    for(int i=1;i<=n;i++) {
        if(t[i]<Ans[i]) {
            for(int j=1;j<=n;j++)
                Ans[j]=t[j];
            return;
        }
        else
            if(t[i]>Ans[i])
                return;
    }
}
int main()
{
    scanf("%d%d%s",&n,&k,s+1);
    Min='z',Max='a';
    for(int i=1;i<=n;i++) {
        Min=min(Min,s[i]);
        Max=max(Max,s[i]);
        s[2*n-i+1]=s[i];
        Ans[i]='z';
    }
    if(Min==Max) {
        printf("%s\n",s+1);
        return 0;
    }
    if(s[n]==Min)
        Check(s,k);
    for(int i=n;i<=2*n;i++)
        if(s[i]==Min)
            Check(s+i-n,k-1);
    printf("%s\n",Ans+1);
}
