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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int k;
string s;
P p[10001];

string get_min(string a,string b){
	if(a=="")return b;
	for(int i=0;i<a.size();i++){
		if(a[i]<b[i])return a;
		if(a[i]>b[i])return b;
	}
	return a;
}

int main(void){
	scanf("%d%d",&n,&k);
	cin >> s;
	string ns="";
	ns=s;
	reverse(ns.begin(),ns.end());
	s+=ns;
	int mn=(s[0]-'a'),cnt=1,now=1;
	for(int i=1;i<s.size();i++){
		if((s[i]-'a')<mn){
			mn=(s[i]-'a');
			now=0;
		}
		if((s[i]-'a')==mn){
			now++;
		}
		if((s[i]-'a')>mn){
			now=0;
		}
		cnt=max(cnt,now);
		p[i]=P((s[i]-'a'),now);
	}
	int cnt_k1=cnt;
	for(int i=1;i<k;i++){
		if(cnt>=n)break;
		cnt*=2;
	}
	if(cnt>=n){
		string ans="";
		for(int i=0;i<n;i++){
			ans+=('a'+mn);
		}
		cout << ans << endl;
		return 0;
	}
	string ans="";
	for(int i=n-1;i<n*2;i++){
		if(p[i]!=P(mn,cnt_k1))continue;
		string tmp="";
		for(int j=0;j<cnt;j++){
			tmp+=s[i];
		}
		int pos=i-cnt_k1;
		while(tmp.size()<n){
			tmp+=s[pos];
			pos--;
		}
		ans=get_min(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}
