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>
using namespace std;
#define N 10050
int n,k,tp;
char s[N],t[N],as[N],as1[N];
void solve()
{
	int le=0,st=n;
	while(t[st]==t[n])le++,st--;
	le<<=(k-1);
	if(le>n)le=n;
	for(int i=1;i<=le;i++)as1[i]=t[n];
	for(int i=le+1,k=st;i<=n;i++,k--)as1[i]=t[k];
	for(int i=1;i<=n;i++)if(as[i]>as1[i]){for(int j=1;j<=n;j++)as[j]=as1[j];return;}
	else if(as[i]<as1[i])return;
}
int main()
{
	scanf("%d%d%s",&n,&k,s+1);
	if(k>=14){char as='z';for(int i=1;i<=n;i++)if(s[i]<as)as=s[i];for(int i=1;i<=n;i++)printf("%c",as);return 0;}
	tp=1<<k-1;
	for(int i=1;i<=n;i++)s[n*2-i+1]=s[i];
	as[1]='z'+1;
	for(int i=n+1;i<=n*2;i++)
	{
		for(int j=i-n+1;j<=i;j++)t[j-i+n]=s[j];
		solve();
	}
	printf("%s",as+1);
}//