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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
 
public class code2 {
	 static class Reader 
	    { 
	        final private int BUFFER_SIZE = 1 << 16; 
	        private DataInputStream din; 
	        private byte[] buffer; 
	        private int bufferPointer, bytesRead; 
	  
	        public Reader() 
	        { 
	            din = new DataInputStream(System.in); 
	            buffer = new byte[BUFFER_SIZE]; 
	            bufferPointer = bytesRead = 0; 
	        } 
	  
	        public Reader(String file_name) throws IOException 
	        { 
	            din = new DataInputStream(new FileInputStream(file_name)); 
	            buffer = new byte[BUFFER_SIZE]; 
	            bufferPointer = bytesRead = 0; 
	        } 
	  
	        public String readLine() throws IOException 
	        { 
	            byte[] buf = new byte[64]; // line length 
	            int cnt = 0, c; 
	            while ((c = read()) != -1) 
	            { 
	                if (c == '\n') 
	                    break; 
	                buf[cnt++] = (byte) c; 
	            } 
	            return new String(buf, 0, cnt); 
	        } 
	  
	        public int nextInt() throws IOException 
	        { 
	            int ret = 0; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	            do
	            { 
	                ret = ret * 10 + c - '0'; 
	            }  while ((c = read()) >= '0' && c <= '9'); 
	  
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        public long nextLong() throws IOException 
	        { 
	            long ret = 0; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	            do { 
	                ret = ret * 10 + c - '0'; 
	            } 
	            while ((c = read()) >= '0' && c <= '9'); 
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        public double nextDouble() throws IOException 
	        { 
	            double ret = 0, div = 1; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	  
	            do { 
	                ret = ret * 10 + c - '0'; 
	            } 
	            while ((c = read()) >= '0' && c <= '9'); 
	  
	            if (c == '.') 
	            { 
	                while ((c = read()) >= '0' && c <= '9') 
	                { 
	                    ret += (c - '0') / (div *= 10); 
	                } 
	            } 
	  
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        private void fillBuffer() throws IOException 
	        { 
	            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
	            if (bytesRead == -1) 
	                buffer[0] = -1; 
	        } 
	  
	        private byte read() throws IOException 
	        { 
	            if (bufferPointer == bytesRead) 
	                fillBuffer(); 
	            return buffer[bufferPointer++]; 
	        } 
	  
	        public void close() throws IOException 
	        { 
	            if (din == null) 
	                return; 
	            din.close(); 
	        } 
	    } 	
	
	public static int[] buildeLCS(String str,int n)
	{
		int[]lcs=new int[n];
		
		int i=1;
		int j=0;
		
		while(i<n)
		{
			if(str.charAt(i)==str.charAt(j))
			{
				lcs[i]=j+1;
				j++;
				i++;
			}
			else
			{
				if(j>0)
				{
					j=lcs[j-1];
				}
				else
				{
					lcs[i]=0;
					j=0;
					i++;
				}
			}
		}
		return lcs;
	}
	public static void match(String txt,String pat)
	{
		int[]lcs=buildeLCS(pat,pat.length());
		int j=0;//pattern pointer
		int i=0;//txt pointer
		while(i<txt.length())
		{
			if(txt.charAt(i)==pat.charAt(j))
			{
				i++;
				j++;
			}
			if(j==pat.length()-1)
			{
				System.out.println("String found at "+(i-j));
				j=lcs[j-1];
			}
			else if(i<txt.length() && txt.charAt(i)!=pat.charAt(j))
			{
				if(j>0)
				j=lcs[j-1];
				else
				i++;
			}
		}	
	}
	
	public static int find(String str,String sub)
	{
		int count=0;
		
		int i=0;
		while(i<sub.length())
		{
			if(sub.charAt(i)==str.charAt(i))
				count++;
			else break;
		}
		
		return count;
	}
	public static void main(String args[]) throws IOException
	{
        Scanner s = new Scanner(System.in);
		//Reader s=new Reader();
        
        int n=s.nextInt();
        int k=s.nextInt();
        
        String str=s.next();
        
        
        int i=0;int j=str.length()-1;
        
        int[]lcs=buildeLCS(str,str.length());
        int count=lcs[str.length()-1];
        int req=str.length()-count;
        //System.out.println("r "+req);
        StringBuilder output=new StringBuilder(str);
        String appendStr=str.substring(str.length()-req);
        for(i=0;i<k-1;i++)
        {
        	output.append(appendStr);
        }
        System.out.println(output.toString());
	    s.close();
	}
 
	 static class Pair{
		int start;int end;
		Pair(int x,int y)
		{
			start=x;
			end=y;
		}
		 @Override
		    public int hashCode() {
		        final int prime = 31;
		        int result = 1;
		        result = prime * result + (start+end); 
		        return result;
		    }
		 
		    //Compare only account numbers
		    @Override
		    public boolean equals(Object obj) {
		        if (this == obj)
		            return true;
		        if (obj == null)
		            return false;
		        if (getClass() != obj.getClass())
		            return false;
		        Pair other = (Pair) obj;
		        if (start != other.start || end!=other.end )
		            return false;
		        return true;
		    }
		 
	}
}