Problem Background

Xiao Bo says this is an excellent introductory string problem, so it is excellent.

Problem Description

Given a string \( s \) containing only uppercase and lowercase letters and digits, determine if \( s \) can be split into at least \( k \) substrings \( s_1, s_2, \dots, s_t \) (where \( t \ge k \)) such that for all \( 1 < i \le t \), \( s_i \) is a substring of \( s_1 s_2 \dots s_{i-1} \) (concatenation of the previous substrings).

A string \( s \) is a substring of another string \( t \) if and only if \( s \) can be obtained by deleting an optional prefix and an optional suffix from \( t \).

Input Format

The first line contains two positive integers \( n \) and \( k \), where \( n \) is the length of \( s \).

The second line contains a string \( s \), consisting only of uppercase and lowercase letters and digits.

Output Format

If no such split is possible, output -1.

Otherwise, the first line should output a positive integer \( t \) (\( t \ge k \)), indicating the number of substrings you are splitting \( s \) into.

The next \( t \) lines should each contain a substring \( s_i \). You must ensure that \( s_1 s_2 \dots s_t = s \).

Sample Input and Output

Sample Input #1

6 2
114514

Sample Output #1

2
1145
14

Sample Input #2

8 2
a1Aa11Aa

Sample Output #2

3
a1A
a1
1Aa

Sample Input #3

11 2
stoImakforz

Sample Output #3

-1

Notes

Sample 1 Explanation

1145|14 is a valid split because it results in 2 substrings and \( 2 \ge k \), and 14 is a substring of 1145.

Sample 2 Explanation

a1A|a1|1Aa is a valid split because it results in 3 substrings and \( 3 \ge k \), and a1 is a substring of a1A, and 1Aa is a substring of a1Aa1.

Sample 3 Explanation

After trying all possible splits, it is found that no split can satisfy the condition.

Data Range

For all data, \( 2 \le k \le n \le 10^6 \) and \( s \) consists only of uppercase and lowercase letters and digits.

见题面 Input 部分

见题面 Output 部分