Problem: You are given a string t consisting of n lowercase Latin letters and an integer number k.

Let's define a substring of some string s with indices from l to r as s[l ... r].

Your task is to construct such string s of minimum possible length that there are exactly k positions i such that s[i ... i + n - 1] = t. In other words, your task is to construct such string s of minimum possible length that there are exactly k substrings of s equal to t.

It is guaranteed that the answer is always unique.

Input

The first line of the input contains two integers n and k (1 ≤ n, k ≤ 50) — the length of the string t and the number of substrings.

The second line of the input contains the string t consisting of exactly n lowercase Latin letters.

Output

Print such string s of minimum possible length that there are exactly k substrings of s equal to t.

It is guaranteed that the answer is always unique.

Examples

Input

3 4
aba


Output

ababababa


Input

3 2
cat


Output

catcat

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void speed() { ios_base::sync_with_stdio(true); }
int main() {
  long long int t = 1;
  while (t--) {
    long long int n, m;
    cin >> n >> m;
    string A;
    cin >> A;
    if (m == 1) {
      cout << A;
      return 0;
    }
    long long int c = 0;
    string R = A, temp = "", B;
    reverse(R.begin(), R.end());
    long long int len = -1;
    set<char> S;
    for (long long int i = 0; i < n; i++) S.insert(A[i]);
    if (S.size() == 1) {
      m--;
      while (m--) cout << A[0];
      cout << A;
      return 0;
    }
    for (long long int i = 1; i <= n - 1; i++) {
      temp = A.substr(0, i);
      B = R.substr(0, i);
      reverse(B.begin(), B.end());
      if (temp == B) len = i;
    }
    string first = "", second = "";
    if (len == -1) {
      long long int k = m;
      while (k--) first += A;
    } else {
      long long int rem = m - 1;
      long long int r = n - len;
      string G = A.substr(0, r);
      while (rem--) first += G;
      first += A;
    }
    string x = "", y = "";
    len = -1;
    for (long long int i = n; i >= 2; i--) {
      x += A[n - i];
      y = R.substr(0, n - i + 1);
      reverse(y.begin(), y.end());
      if (x == y) len = (n - i + 1);
    }
    if (len == -1) {
      for (long long int i = 1; i <= m; i++) {
        second += A;
      }
    } else {
      long long int rem = n - len;
      string X = R.substr(0, rem);
      reverse(X.begin(), X.end());
      second += A;
      m--;
      while (m--) {
        second += X;
      }
    }
    if (first.size() < second.size())
      cout << first;
    else
      cout << second << "\n";
  }
}