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

Solution:
def lps(pattern):
    pattern = '#'+pattern  
    length = len(pattern)
    table = [0 for i in range(length)] 
    
    table[1] = 0
    
    for i in range(2, length):
        j = table[i-1]  
        while pattern[j+1] != pattern[i] and j>0:
            j = table[j]   
            
        if pattern[j+1] == pattern[i]:  
            table[i] = j+1 
            
    return table 

def solve(t, k):
    
    if k==1:
        return t
    table = lps(t) 
    p = table[-1]
    if p==0:
        return t*k
    s = t[:-p]
    return s*(k) + t[-p:]   
        
    
                    


if __name__ == '__main__':
    n, k = map(int, input().split()) 
    t = input()
    print(solve(t, k))