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;
string greedy(string s, int k){
	if (k == 0) return s;
	int n = s.size();
	while (k > 1){
		int take = 1;
		while (take < n && s[n-take-1] == s[n-1]) take++;
		string t = "";
		for (int i=0; i < n-take;i++) t += s[take+i];
		for (int i=0; i < take; i++) t += s[n-i-1];
		s = t;
		k--;
	}
	int take = 1;
	while (take < n && s[n-take-1] == s[n-1]) take++;
	string t = "";
	for (int i=0; i < take;i++) t += s[n-take+i];
	for (int i=0; i < n-take; i++) t += s[n-i-1];
	return t;
}
signed main() {
	#ifdef LOCAL
		freopen("H_input.txt", "r", stdin);
		//freopen("C_output.txt", "w", stdout);
	#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    k = min(k, 15);
    string res = "";
    for (int i=0; i < n; i++) res += 'z';
    string t = s;
	reverse(t.begin(), t.end());
	s += t;
	for (int i=0; i <= n; i++){
		string var = "";
		for (int j=0; j < n; j++) var += s[i+j];
		res = min(res, greedy(var, k-1));
	}
	cout << res;
}