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;

namespace TYC
{
	typedef long long ll;
	const int N = 5005;

	int n, k, L[N];
	char S[N << 1], Ans[N], R[N];

	void solve(int p, int len)
	{
		if (p + len - 1 != n)
		{
			p = n - p - len + n + 2;
			len = len * (1 << min(k - 1, 16));
		}
		else
			len = len * (1 << min(k, 16));
		if (len >= n)
		{
			for (int i = 1; i <= n; i++)
				putchar(S[p]);
			exit(0);
		}
		for (int i = 1; i <= len; i++)
			R[i] = S[p];
		for (int i = 1; i <= n - len; i++)
			R[len + i] = S[p - i];
		for (int i = 1; i <= n; i++)
			if (R[i] != Ans[i])
			{
				if (R[i] < Ans[i])
					memcpy(Ans, R, sizeof(char[n + 1]));
				break;
			}
	}

	void work()
	{
		scanf("%d%d%s", &n, &k, S + 1);
		char minc = S[1];
		int maxl = 0;
		for (int i = 1; i <= n; i++)
			minc = min(minc, S[i]);
		for (int i = 1; i <= n; i++)
			if (S[i] == minc)
				maxl = max(maxl, L[i] = S[i] == S[i - 1] ? L[i - 1] + 1 : 1);
		for (int i = 1; i <= n; i++)
			S[i + n] = S[n - i + 1];
		Ans[1] = char('z' + 1);
		for (int i = 1; i <= n; i++)
			if (L[i] == maxl || i == n)
				solve(i - L[i] + 1, L[i]);
		puts(Ans + 1);
	}
}

int main()
{
	TYC::work();
	return 0;
}