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(){
	ios_base::sync_with_stdio(false); 
  cin.tie(NULL); cout.tie(NULL); 

  string s; int k, n;
  cin >> n >> k >> s;

  vector < int > cnt(n, 0);
  char best = *min_element(s.begin(), s.end());



  if(k > 15) {
    for(int i = 0; i < n; ++i) cout << best;
  }
  else {
    if(k == 1) {
      string t = s, ans = s; reverse(t.begin(), t.end()); 
      s += t;
      for(int i = 0; i < n + 1; ++i) {
        if(ans > s.substr(i, n)) ans = s.substr(i, n);
      }
      cout << ans;
      return 0;
    }

    string t = s;
    reverse(t.begin(), t.end());
    
    string ans = s;

    s += t;

    k -= 1;

    int cnt = 0;
    for(int i = s.size() - 1; i >= 0; --i) {
      if(s[i] == best) cnt++;
      else {
        cnt = 0;
      } 

      int get = min(n, cnt << k);
  //    cout << cnt << endl;
      if(i < n - cnt) {
    //    cout << "bug" << endl;
        continue;
      }

      string tmp = s.substr(i - n + get, n - get);
      reverse(tmp.begin(), tmp.end());

      ans = min(ans, string(get, best) + tmp);
    }

    cout << ans;
  }


  return 0;
}