I. Improving Chewing Candy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have obtained a job in a thriving candy factory, which has recently acquired a specialized machine for producing chewy candy. Your job's objective is to maximize this machine's output, producing unique candy chains never before seen in the market.

The peculiarity of this machine is that it only produces circular chains of chewy candy blocks, represented by the letters of the English alphabet, from 'a' to 'z'. If two blocks are represented by the same letter, that means they share the same flavor.

Your challenge is to obtain a straight line of candy blocks from the circular chain, which is as long as possible without being cloying. We define a chain as "cloying" if it contains more than $$$k$$$ blocks of the same flavor. However, due to the sticky nature of the chewy candy blocks, once you select a block of a particular flavor, you must take all adjacent blocks of the same flavor.

For instance, suppose $$$k = 2$$$ and you have a circular chain of chewy candy represented by "abbcdaa". The longest chain of chewy candy you can obtain without it being cloying is "bbcd". You cannot select any 'a' flavored block, as these blocks are stuck together, forming a continuous block of "aaa", and would exceed the $$$k$$$ limit.

Your task is to determine the longest candy chain that you can extract from the machine without it being cloying.

Input

The input consists of two lines:

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \leq n \leq 10^6; 1 \leq k \leq 10^6)$$$, representing the number of blocks in the circular chain and the maximum number of blocks of the same flavor that can be had in a chewy candy chain without it being cloying, respectively.

The second line contains a string $$$s$$$ of size $$$n$$$, representing the circular chain of chewy candy blocks produced by the machine. Each character of the string corresponds to a block of a flavor, with the English alphabet letters, from 'a' to 'z'.

Output

If there is no possible candy chain, print -1.

Otherwise, print two lines:

In the first line, print the length of the longest possible chewy candy chain according to the previous conditions.

In the second line, print the found chain. If there are multiple solutions, print any of them.

Examples
Input
9 2
aabccbaba
Output
5
bccba
Input
3 4
aaa
Output
-1