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<cmath>
#include<algorithm>
using namespace std;
const int N=10005;
int n,k;
char mi,mx,s[N],t[N],ans[N];
void ckmin(){
	bool flag=false;
	for(int i=1;i<=n;i++){
		if(t[i]>ans[i]){
			break;
		}else if(t[i]<ans[i]){
			flag=true;
			break;
		}
	}
	if(flag){
		for(int i=1;i<=n;i++){
			ans[i]=t[i];
		}
	}
}
void gao(char s[],int k){
	int len=1;
	while(len<n&&s[n-len]==mi){
		len++;
	}
	int now=n-len+1;
	while(k&&len<n){
		len*=2;
		k--;
	}
	if(len>=n){
		for(int i=1;i<=n;i++){
			t[i]=mi;
		}
		ckmin();
	}else{
		for(int i=1;i<=len;i++){
			t[i]=mi;
		}
		for(int i=len+1;i<=n;i++){
			t[i]=s[--now];
		}
		ckmin();
	}
}
int main(){
	scanf("%d%d%s",&n,&k,s+1);
	mi='z',mx='a';
	for(int i=1;i<=n;i++){
		s[2*n-i+1]=s[i];
		mi=min(mi,s[i]);
		mx=max(mx,s[i]);
		ans[i]='z';
	}
	if(mx==mi){
		puts(s+1);
		return 0;
	}
	if(s[n]==mi){
		gao(s,k);
	}
	for(int i=n;i<=2*n;i++){
		if(s[i]==mi){
			gao(s+i-n,k-1);
		}
	}
	puts(ans+1);
	return 0;
}