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<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<(int)(n);i++)
#define N 200010


int main() {
	char a[N];
	char b[N];
	f(i, N) {
		a[i] = 0;
		b[i] = 0;
	}
	int n, k;
	int x, y, z;
	int s, ans;
	bool v = true;
	ans = 0;
	scanf("%d %d", &n, &k);
	scanf("%s", a);
	f(i, n) {
		a[(2 * n - i - 1)] = a[i];
		b[i] = a[i];
	}
	for (int i = 1; i <= n; i++) {
		f(j, n) {
			if (a[i + j] < b[j]) {
				f(ii, n)b[ii] = a[i + ii];
				break;
			}
			else if (a[i + j] > b[j])break;
		}
	}
	k = min(k - 1, 20);
	f(kk, k) {
		x = 0;
		f(i, n) {
			if (b[i] == b[0])x++;
			else break;
		}
		for (int i = n - 1; i >= x; i--) {
			b[i] = b[i - x];
		}
		f(i, x)b[i] = b[0];

	}
	printf("%s\n", b);


	return 0;
}