Cyclic shift and search for duplicate substrings

C# Hard loops

Task «Cyclic shift and search for duplicate substrings»

Given a string S consisting of lowercase Latin letters. It is necessary to perform a cyclic left shift of the string by K positions (K can be greater than the length of the string). After the shift, find all non-overlapping repeating substrings of length L (L is given) in the new string. A repeating substring is a substring that occurs in the string two or more times, and its occurrences must not overlap. Output the number of such substrings and the substrings themselves in lexicographic order. If there are no such substrings, output 0.

Input Format

In the first line, an integer N (1 ≤ N ≤ 1000) — the length of the string. In the second line, the string S itself. In the third line, an integer K (0 ≤ K ≤ 10^9) — the number of shifts. In the fourth line, an integer L (1 ≤ L ≤ N) — the length of the substring.

Output Format

In the first line, output an integer M — the number of unique non-overlapping repeating substrings of length L. If M > 0, in the next M lines output the substrings themselves in lexicographic order.

Examples

Example 1

INPUT

5
abcde
3
2

OUTPUT

0

Example 2

INPUT

10
abracadabra
5
4

OUTPUT

1
abra

main.cs