#60 쉬운 문자열 문제

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, rd, and th letter of .

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.

Subtasks

#	Score	Constraints
1	20	$S_1=S_2=\cdots=S_N$ .

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 b.