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<cstring>
#include<algorithm>
using namespace std;
int n,k,last,mx,len;
char a,s[10010],ans[5050]={0,'z'},now[5050];
void work(int l)
{
	for(int i=1;i<=len;++i)now[n-len+i]=s[l-mx+1-i];
	for(int i=1;i<=n-len;++i)now[i]=a;
	for(int i=1;i<=n;++i)
		if(now[i]!=ans[i])
		{
			if(now[i]<ans[i])swap(now,ans);
			return ;
		}
}
int main()
{
	scanf("%d %d",&n,&k);
	scanf("%s",s+1);
	a='z';
	for(int i=1;i<=n;++i)s[2*n+1-i]=s[i],a=min(a,s[i]);
	if(k>=14)
	{
		for(int i=1;i<=n;++i)putchar(a);
		return 0;
	}	
	last=1,mx=0,len;
	for(int i=1;i<=2*n+1;++i)
		if(s[i]!=a)mx=max(mx,i-last),last=i+1;
	len=mx;
	for(int i=1;i<k;++i)len<<=1;
	if(len>=n)
	{
		for(int i=1;i<=n;++i)putchar(a);
		return 0;
	}
	len=n-len;
	last=1;
	for(int i=1;i<=2*n+1;++i)
		if(s[i]!=a)
		{
			if(i-last==mx&&i-1>=n)work(i-1);
			last=i+1;
		}
	for(int i=1;i<=n;++i)putchar(ans[i]);
	return 0;
}
