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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,k;

char s[10050],ans[10050];

int main()
{
	n=read(),k=read();
	cin >> (s+1);
	for (int i=1;i<=n;i++)
		s[n*2-i+1]=s[i];
	for (int i=1;i<=n;i++)
		ans[i]=s[i];
	for (int i=1;i<=n;i++)
	{
		bool flag=true;
		for (int j=i;j<=n+i-1 && flag;j++)
		{
			if (ans[j-i+1]<s[j])
				flag=false;
			else if (ans[j-i+1]>s[j])
				break;
		}
		if (flag)
		{
			for (int j=i;j<=n+i-1;j++)
				ans[j-i+1]=s[j];
		}
	}
	int len=1;
	while (len<=n && ans[len]==ans[1])
		len++;
	len--;
	if (k>15 || len*(1<<(k-1))>=n)
	{
		for (int i=1;i<=n;i++)
			cout << ans[1];
	}
	else
	{
		int res=n-(len*(1<<(k-1)));
		for (int i=1;i<=n-res;i++)
			cout << ans[1];
		for (int i=1;i<=res;i++)
			cout << ans[i+len];
	}
	return 0;
}