## Algorithm

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 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[lr]�[�…�].

Your task is to construct such string s of minimum possible length that there are exactly k positions i such that s[ii+n1]=t�[�…�+�−1]=�. 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 (1n,k501≤�,�≤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
Copy
3 4aba
output
Copy
ababababa
input
Copy
3 2cat
output
Copy
catcat

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int n, k;
string t, s;

int main() {
cin >> n >> k >> t;

for(int cnt = 0, l = 1; cnt < k; ++cnt) {
bool ok = true;
int i, j = 0;

for(; l < s.length(); ++l) {
ok = true;
for(i = l, j = 0; i < s.length() && j < t.length(); ++i, ++j)
if(s[i] != t[j]) {
ok = false;
break;
}

if(ok)
break;
}

for(int i = j; i < t.length(); ++i)
s += t[i];

l = s.length() - t.length() + 1;
}

cout << s << endl;

return 0;
}
Copy The Code &

Input

cmd
3 4
aba

Output

cmd
ababababa