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 JAVA):

Solution:


import java.util.*;

public class main {
    
    static int KMPSearch(String pat, String txt)
	{
		int M = pat.length();
		int N = txt.length();

		// create lps[] that will hold the longest
		// prefix suffix values for pattern
		int lps[] = new int[M];
		int j = 0; // index for pat[]

		// Preprocess the pattern (calculate lps[]
		// array)
		return computeLPSArray(pat, M, lps);

		
	}

	static int computeLPSArray(String pat, int M, int lps[])
	{
		// length of the previous longest prefix suffix
		int len = 0;
		int i = 1;
		lps[0] = 0; // lps[0] is always 0

		// the loop calculates lps[i] for i = 1 to M-1
		while (i < M) {
			if (pat.charAt(i) == pat.charAt(len)) {
				len++;
				lps[i] = len;
				i++;
			}
			else // (pat[i] != pat[len])
			{
				// This is tricky. Consider the example.
				// AAACAAAA and i = 7. The idea is similar
				// to search step.
				if (len != 0) {
					len = lps[len - 1];

					// Also, note that we do not increment
					// i here
				}
				else // if (len == 0)
				{
					lps[i] = len;
					i++;
				}
			}
		}
                return lps[lps.length-1];
                /*
		for( i=0;i<lps.length;i++){
		    System.out.print(lps[i]+" ");
		}
		System.out.println();*/
	}
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        String s = in.next();
        int i = 0,j = 1;
        int c = 0,curr= 0;
        /*for(i=0;i<s.length();i++){
            if(j>=s.length()){
                c = curr;
                break;
            }
            else if(s.charAt(i)==s.charAt(j)){
                curr++;
                j++;
            }
            else{
                
                if(i==0)
                    j++;
                i = -1;
                curr = 0;
            }
            //System.out.println(i+" "+j);
        }*/
        //c = Math.max(c, curr);
        //System.out.println(c);
        c = KMPSearch(s,s);
        String ans = s;
        if(c==0){
            while(--m>0){
                ans+=s;
            }
        }
        else{
            while(--m>0){
                ans+=s.substring(c);
            }
        }
        System.out.println(ans);
    }

}