#60 쉬운 문자열 문제

Loading problem...

Preparing the statement, recent submissions, and submit form.

#60 쉬운 문자열 문제

DOJ/Beginner Contest DOJ/BCD 1

Authors: lunarlity

Time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

A string $S$ of length $N$ is given.

You need to construct a string $T$ of length $M$ . The number of times $S$ appears as a substring in $T$ must be maximized. The appearances of the substring may overlap.

For example, if $S=$ dada and $T=$ dadadadas, $S$ appears in $T$ a total of $3$ times, each starting from the $1$ st, $3$ rd, and $5$ th letter of $T$ .

Input

The input is given in the following format.

$N\ M$ $S$

Output

Print the answer in the following format.

$T$

If there are multiple strings that satisfy the condition, you may print any of them.

Constraints

$1 \le N \le 7\ 000$ .
$1 \le M \le 7\ 000$ .
$S$ consists only of lowercase English letters.
The output string $T$ must also consist only of lowercase English letters.

Subtasks

#	Score	Constraints
1	20	$S_1=S_2=\cdots=S_N$ .
2	30	The character identical to $S_1$ appears exactly once in $S$ .
3	50	No additional constraints.

Samples

Input

4 9
dada

Output

dadadadas

Notes

$S_i$ denotes the $i$ -th character of the string $S$ . For example, if $S=$ abcac, then $S_2=$ b.