A. Many Equal Substrings

time limit per test :1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

You are given a string ttnnkk

Let's define a substring of some string ss with indices from ll to rr as s[l…r]s[l…r].

Your task is to construct such string ss of minimum possible length that there are exactly kk positions ii such that s[i…i+n−1]=ts[i…i+n−1]=t. In other words, your task is to construct such string ss of minimum possible length that there are exactly kk substrings of ss equal to tt.

It is guaranteed that the answer is always unique.

Input

The first line of the input contains two integers nn and kk (1≤n,k≤501≤n,k≤50) — the length of the string tt and the number of substrings.

The second line of the input contains the string tt consisting of exactly nn lowercase Latin letters.

Output

Print such string ss of minimum possible length that there are exactly kk substrings of ss equal to tt.

It is guaranteed that the answer is always unique.

Examples

input:

3 4

aba

output:

ababababa

input:

3 2

cat

output:

catcat

题意：

输出一个字符串使得给定长度为n的字符串在其中出现k次，求符合条件的长度最小的字符串，我们只要求出"循环节"即可，举个例子：给我们的字符串是"abcab"，不要把该字符串的循环节看作1，应该是3，这就是这题构造字符串的核心，因为我们构造的时候会循环一部分字符串，接着上面的列子说：abc(abc)(abc)(abc)ab，我们输出k次循环节，然后输出原字符串除去循环节的部分，代码如下:

 for(int i=1; i<=n; i++)
        {
            int flag=1;
            for(int j=0; j+i<n; j++)
            {
                if(str[j]!=str[j+i])
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                num=i;
                break;
            }
        }

ac代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,num;
string str;
int main()
{
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        cin>>str;
        for(int i=1; i<=n; i++)
        {
            int flag=1;
            for(int j=0; j+i<n; j++)
            {
                if(str[j]!=str[j+i])
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                num=i;
                break;
            }
        }
        string str1=str.substr(0,num);
        string str2=str.substr(num);
        for(int i=1;i<=k;i++)
            cout<<str1;
        cout<<str2<<endl;
    }
    return 0;
}