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 main(){
	int n, k; cin >> n >> k;
	string s, t; cin >> s;
	t = s; reverse(t.begin(), t.end());
	s += t;
	struct opt {
		int start;
		int size;
		char c;
	};
	string ans(n, 'z');
	if(k == 1){
		for(int i = 0; i <= n; i++){
			string now = s.substr(i, n);
			if(now < ans) ans = now;
		}
		cout << ans << endl;
		return 0;
	}
	for(int i = 0; i <= n; i++){
		opt now = {i, 0, s[i + n - 1]};
		for(int j = i + n - 1; j >= i && s[j] == now.c; j--, now.size++);
		int first_off = i + n - 1 - now.size;
		for(int j = 0; j < k - 2 && now.size < n; j++){
			now.size *= 2;
		}
		string here;
		int len_here = 0;
		for(int j = 0; len_here < n && j < now.size; j++){
			here.push_back(now.c);
			len_here++;
		}
		for(int j = first_off; len_here < n && j >= i; j--){
			here.push_back(s[j]);
			len_here++;
		}
		reverse(here.begin(), here.end());
		string up = here;
		reverse(up.begin(), up.end());
		here += up;
		int p = n - 1;
		while(p >= 0 && here[p] == here[n - 1]) p--;
		p++;
		string tr = here.substr(p, n);
		if(tr < ans) ans = tr;
	}
	cout << ans << endl;
	return 0;
}
