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<algorithm>
using namespace std;
const int MAXN = 5000;
char str[2*MAXN + 5], mn;
char ans[MAXN + 5];
int N, K;
bool check(char *S) {
	for(int i=1;i<=N;i++)
		if( ans[i] != S[i] )
			return ans[i] > S[i];
	return false;
}
void update(char *S) {
	for(int i=1;i<=N;i++)
		ans[i] = S[i];
}
int pw[35];
char S[MAXN + 5];
int main() {
	pw[0] = 0, pw[1] = 2;
	for(int i=2;i<=30;i++) pw[i] = 2*pw[i-1];
	scanf("%d%d%s", &N, &K, str + 1);
	mn = 'z';
	for(int i=1;i<=N;i++)
		mn = min(mn, str[i]), ans[i] = 'z';
	if( K >= 30 ) {
		for(int i=1;i<=N;i++)
			putchar(mn);
	}
	else {
		for(int i=1;i<=N;i++)
			str[2*N - i + 1] = str[i];
		int cnt = 0;
		for(int i=1;i<N;i++)
			cnt = (str[i] == str[i-1]) ? cnt + 1 : 1;
		for(int i=N;i<=2*N;i++) {
			cnt = (str[i] == str[i-1]) ? cnt + 1 : 1;
			if( pw[K - 1] <= N/cnt ) {
				for(int j=1;j<=pw[K-1]*cnt;j++)
					S[j] = str[i];
				int k = i - cnt;
				if( K == 1 ) k = i;
				for(int j=pw[K-1]*cnt+1;j<=N;j++)
					S[j] = str[k--];
			}
			else {
				for(int j=1;j<=N;j++)
					S[j] = str[i];
			}
			if( check(S) ) update(S);
		}
		puts(ans + 1);
	}
}