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.io.*;

import java.util.*;
 public class Solution {
	 public static void main(String[] args) throws Exception
    {
		 FastReader fr=new FastReader();
		 int n=fr.nextInt();
		 int k=fr.nextInt();
		 String t=fr.next();
		 int a[]=new int[n];
		 for(int i=1;i<t.length();i++) {
			 int j=a[i-1];
			 while(j>0&&t.charAt(i)!=t.charAt(j)) {
				 j=a[j-1];
			 }
			 if(t.charAt(i)==t.charAt(j))
				 j++;
			 a[i]=j;
		 }
		 
		 int len=t.length()-a[n-1];
		 for(int i=0;i<k-1;i++) {
			 System.out.print(t.substring(0,len));
		 }
		 System.out.print(t);
			
		 
		  
            
    }
	 public static String reverse(String s) {
		 String res="";
		 for(int i=0;i<s.length();i++) {
			 res+=s.charAt(i);
		 }
		 return res;
	 }
	 public static int to_int(String s) {
		 int r=0;
		 for(char c:s.toCharArray()) {
			 r=(r*10)+(c-'0');
		 }
		 return r;
	 }
	 public static boolean valid(StringBuilder a,StringBuilder b,Map<Character,Character> map,int h,int m) {
		
		for(int i=0;i<a.length();i++) {
			char c=a.charAt(i);
			if(map.containsKey(c)) {
				a.deleteCharAt(i);
			   a.insert(i, map.get(c));
			}
			else
				return false;
			
		}
		for(int i=0;i<b.length();i++) {
			char c=b.charAt(i);
			if(map.containsKey(c)) {
				b.deleteCharAt(i);
			   b.insert(i, map.get(c));
			}
			else
				return false;
			
		}
		 String q=reverse(a.toString());
		 String r=reverse(b.toString());
		 int ax=to_int(q);
		 int bx=to_int(r);
		 
		 return ax<m&&bx<h;
	 }
	 public static int bsearch(long suf[],long val) {
		 int i=0;
		 int j=suf.length-1;
		 while(i<=j) {
			 int mid=(i+j)/2;
			 if(suf[mid]==val)
				 return mid;
			 else if(suf[mid]<val)
				 j=mid-1;
			 else
				 i=mid+1;
		 }
		 return -1;
	 }
	 
	 
	 
	public static boolean check(String s) {//balanced para
		Stack<Character> st=new Stack<>();
		//System.out.println(s);
		for(char c:s.toCharArray()) {
			if(c=='(')
				st.push(c);
			else {
				if(st.isEmpty())
					return false;
				else if(st.peek()=='(')
					st.pop();
			}
		}
		if(!st.isEmpty())
			return false;
		else
			return true;
	}
	 
	 
	 public static void print(String str) {
		 System.out.println(str);
	 }
	public static int[] getFreq(String s) {
		int a[]=new int[26];
		for(int i=0;i<s.length();i++) {
			a[s.charAt(i)-'a']++;
		}
		return a;
		
	}
	 
	 public static boolean isPrime(int n) {
		 
		 for(int i=2;(i*i)<=n;i++) {
			 if(n%i==0)
				 return false;
		 }
		 return true;
	 }
            	  
             
             
    }
 class Pair{
	 int x;
	 int y;
	 long cost;
	 Pair(int x,int y,long cost){
		 this.x=x;
		 this.y=y;
		 this.cost=cost;
	 }
 }
	
	 
	
	

	 
 
  

class FastReader
{
    BufferedReader br;
    StringTokenizer st;
 
    public FastReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }
 
    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    int nextInt()
    {
        return Integer.parseInt(next());
    }
 
    long nextLong()
    {
        return Long.parseLong(next());
    }
 
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
 
    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}