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.math.BigInteger;
import java.util.*;

public class SuperClasss {
    static class Run{
        static void main() {
            int n = in.nextInt(), k = in.nextInt() - 1, ans = 0, i;
            String s = in.next();
            int z[] = z_function(s);
            for(i = 0; i<n; i++){
                if(i+z[i]==n) break;
            }
            String res = s.substring(0, i);
            for(i = 0; i<k; i++)
                print(res);
            print(s);
        }
    }

    public static void main(String[] args){
        Run.main();
        out.flush();
    }

    static final String abc = "abcdefghijklmnopqrstuvwxyz";
    static final int INF = Integer.MAX_VALUE;
    static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(System.out);
    static StreamTokenizer in1 = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedReader in2 = new BufferedReader(new InputStreamReader(System.in));

    static int[] z_function(String s){
        int n = size(s);
        int z[] = new int[n];
        for(int i = 1, l = 0, r = 0; i<n; i++){
            if(i<=r){
                z[i] = min(r-i+1, z[i-l]);
            }
            while(i+z[i]<n && s.charAt(z[i])==s.charAt(i+z[i]))
                z[i]++;
            if(i+z[i]-1>r){
                l = i;
                r = i+z[i]-1;
            }
        }
        return z;
    }

    static long phi(int n){
        long res = n;
        for(int i = 2; i*i<=n; i++){
            if(n%i==0) {
                while (n % i == 0)
                    n /= i;
                res -= res / i;
            }
        }
        if(n>1) res-=res/n;
        return res;
    }

    static char[] strToArray(String s){
        return s.toCharArray();
    }

    static char[] strToArray(StringBuilder s){
        return new String(s).toCharArray();
    }

    static char chAt(String s, int pos){
        return s.charAt(pos);
    }

    static char chAt(StringBuilder s, int pos){
        return s.charAt(pos);
    }

    static int[] prefix_function(String s, String t){
        String edit = s+"#"+t;
        return prefix_function(edit);
    }

    static int[] prefix_function(String s){
        int len = s.length(), pi[] = new int[len];
        for(int i = 1; i<len; i++){
            int j = pi[i-1];
            while(j>0 && s.charAt(i)!=s.charAt(j)) j = pi[j-1];
            if(s.charAt(i)==s.charAt(j)) j++;
            pi[i] = j;
        }
        return pi;
    }

    static int size(String obj){
        return obj.length();
    }

    static int size(StringBuilder obj){
        return obj.length();
    }

    static int size(Collection<?> obj){
        return obj.size();
    }

    static int size(AbstractMap<?, ?> obj){
        return obj.size();
    }

    static int size(AbstractCollection<?> obj){
        return obj.size();
    }

    static<T> int size(T[] obj){
        return obj.length;
    }

    static <T> void print(T... args) {
        for (T x : args) {
            out.print(x.toString());
        }
    }

    static <T> void println(T... args) {
        print(args);
        out.println();
    }

    static long nextLong() {
        try {
            in1.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (long) in1.nval;
    }

    static int nextInt() {
        try {
            in1.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in1.nval;
    }

    static String nextLine(){
        return in.nextLine();
    }

    static String nextString() {
        try {
            return in2.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    static String next(){
        return in.next();
    }

    static char nextChar() {
        try {
            return (char) in2.read();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return '!';
    }

    static void readArray(int[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextInt();
    }

    static void readArray(long[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextInt();
    }

    static void readArray(char[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextChar();
    }

    static void readArray(String[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextString();
    }

    static void readArray(StringBuilder[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = new StringBuilder(nextString());
    }

    static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }


    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    static int min(int...args){
        Arrays.sort(args);
        return (args[0]);
    }

    static int max(int...args){
        Arrays.sort(args);
        return(args[args.length-1]);
    }

    static double s(int x1, int y1, int x2, int y2, int x3, int y3) {
        return Math.abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2.0;
    }

    static ArrayList<Integer> isPrimeList(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        boolean prime[] = new boolean[n];
        Arrays.fill(prime, true);
        prime[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (prime[i])
                for (int j = i * i; j < n; j += i)
                    prime[j] = false;
        }
        for (int i = 2; i < n; i++)
            if (prime[i]) res.add(i);
        return res;
    }

    static BigInteger bigSqrt(BigInteger n) {
        BigInteger a = BigInteger.ONE.shiftLeft((n.bitLength() + 1) / 2), next = a.subtract(BigInteger.ONE);
        while (next.compareTo(a) < 0) {
            a = next;
            next = a.add(n.divide(a)).divide(BigInteger.valueOf(2));
        }
        return a;
    }

    static<T> ArrayList<T> assign(int size, T obj){
        ArrayList res = new ArrayList(size);
        for(int i = 0; i<size; i++) res.add(obj);
        return res;
    }
}