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>
using namespace std;

int N , K , L , mx; string S , T; char mn = 127;

string work(int pos){
	pos = 2 * N - pos - 1;
	int len = L; for(int i = 1 ; i < K ; ++i) len <<= 1;
	return string(len , mn) + string(T , pos + mx , N - len);
}

int main(){
	cin >> N >> K >> S; T = S;
	reverse(T.begin() , T.end()); T = S = S + T;
	reverse(T.begin() , T.end());
	for(int i = 0 ; i < (int)S.size() ; ++i) mn = min(mn , S[i]);
	for(int i = 0 ; i < (int)S.size() ; ++i) mx = max(mx , L = S[i] == mn ? L + 1 : 0);
	L = mx;
	for(int i = 1 ; i < K && L < N ; ++i) L <<= 1;
	if(L >= N){cout << string(N , mn); return 0;}
	string ans; L = 0;
	for(int i = 0 ; i < (int)S.size() ; ++i){
		L = S[i] == mn ? L + 1 : 0;
		if(i >= N && L == mx){string T = work(i); if(ans.empty() || ans > T) ans = T;}
	}
	cout << ans;
	return 0;
}