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;

const int N = 5005;
int n, k;
char s[N];

int main() {
	cin >> n >> k >> s + 1;
	char a = *min_element(s + 1, s + 1 + n);
	int L = 0;
	for (int i = 1, j; i <= n; )
		if (s[i] == a) {
			for (j = i; j <= n && s[j] == a; ++j);
			L = max(L, j - i);
			i = j;
		} else ++i;
	if (L << min(15, k - 1) >= n) {
		for (int i = 1; i <= n; ++i) cout << a;
		cout << endl;
		return 0;
	}
	string ans;
	for (int i = 1, j; i <= n; )
		if (s[i] == a) {
			for (j = i; j <= n && s[j] == a; ++j);
			if (j - i == L) {
				string now;
				for (int x = 1; x <= L << k - 1; ++x) now += a;
				for (int x = j; now.size() < n; ++x) now += s[x <= n ? x : 2 * n + 1 - x];
				if (ans.empty() || now < ans) ans = now;
			}
			i = j;
		} else ++i;
	if (s[n] == a) {
		string now;
		int i = n;
		while (i && s[i] == a) --i;
		for (int x = 1; x <= n - i << k; ++x) now += a;
		for (int x = i; now.size() < n; --x) now += s[x];
		if (ans.empty() || now < ans) ans = now;
	}
	cout << ans << '\n';
}
