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 Main {

	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		String l = br.readLine();
		String output = "";
		String auxS;
		
		if(n==1) {
			auxS =l;
		}else if(n==2 && l.charAt(0)!=l.charAt(1))
			auxS =l;
		else {
			auxS = firstWay(l, n);
			auxS = (auxS.equals(l))?secondWay(l, n):auxS;
		}
		
		output += l;
		for (int i = 1; i < k; i++) {
			output += auxS;
		}

		pw.print(output);
		pw.flush();
		pw.close();
	}
	
	public static String firstWay(String l, int n) {
		String auxS = l;
		StringTokenizer dividers = getDividers(n);
		int tokens = dividers.countTokens();
		
		for (int i = 0; i < tokens; i++) {
			int k = Integer.parseInt(dividers.nextToken());
			String[] aux = new String[n/k];
			int index = 0;
			for (int j = 0; j < l.length(); j+=k) {
				aux[index] = l.substring(j, k+j);
				index++;
			}
			boolean same = true;
			for (int j = 0; j < aux.length-1; j++) {
				if (!aux[j].equals(aux[j+1])) {
					same = false;
					break;
				}
			}
			if(same) {
				char[] auxC = l.toCharArray();
				for (int m = k; m < auxC.length; m++) {
					auxC[m]=' ';
				}
				auxS = String.valueOf(auxC);
				auxS = auxS.trim();
				
				break;
			}
		}
		
		return auxS;
	}
	
	private static StringTokenizer getDividers(int n) {
		StringBuilder aux = new StringBuilder();
	    for(int i = 1 ; i <n ; i++){
	        if(n%i==0){
	            aux.append(i + " ");
	        }
	    }
	    return new StringTokenizer(aux.toString());  
	}
	
	public static String secondWay(String l, int n) {
		String sub1;
		String sub2;
		if(n%2==0) {
			sub1 = l.substring((n/2)-1, n);
			sub2 = l.substring(0,(n/2)+1);
			char[]aux;
			String auxS = "";
			if(sub1.equals(sub2)) {
				aux = l.toCharArray();
				for (int m = 0; m < sub1.length(); m++) {
					aux[m]=' ';
				}
				auxS = String.valueOf(aux);
				auxS = auxS.trim();
			}else {
				if(sub2.length()>1) {
					int j=sub2.length()-1;
					for (int i = 1; i<sub1.length(); ) {
						sub1 = sub1.substring(i);
						sub2 = sub2.substring(0,j);
						j--;
						if(sub1.equals(sub2)) {
							aux = l.toCharArray();
							for (int m = 0; m < sub1.length(); m++) {
								aux[m]=' ';
							}
							auxS = String.valueOf(aux);
							auxS = auxS.trim();
							break;
						}
					}
					
					if(auxS.equals(""))
						auxS = l;
				}
			}
			
			return auxS;
		}else {
			sub1 = l.substring((n/2), n);
			sub2 = l.substring(0,(n/2)+1);
			char[]aux;
			String auxS = "";
			if(sub1.equals(sub2)) {
				aux = l.toCharArray();
				for (int m = 0; m < sub1.length(); m++) {
					aux[m]=' ';
				}
				auxS = String.valueOf(aux);
				auxS = auxS.trim();
			}else {
				if(sub2.length()>1) {
					int j=sub2.length()-1;
					for (int i = 1; i < sub1.length(); ) {
						sub1 = sub1.substring(i);
						sub2 = sub2.substring(0,j);
						j--;
						if(sub1.equals(sub2)) {
							aux = l.toCharArray();
							for (int m = 0; m < sub1.length(); m++) {
								aux[m]=' ';
							}
							auxS = String.valueOf(aux);
							auxS = auxS.trim();
							break;
						}
					}
					
					if(auxS.equals(""))
						auxS = l;
				}
			}
			
			return auxS;
		}
	}
}