novel

novel

Adrian has every reason to be content. Ever since he and Laura got together, everything's been going great for him. He's even written a short novel about love and heroism. He's considering actually publishing it someday.
However, he's not feeling like himself today. His girlfriend, after having read the novel, told him:
"Honey, I'm thrilled. You write very nicely and you show talent. However, I just thought I'd tell you that, while reading, I had that feeling of "deja vu". More exactly, I sometimes had the impression that I was reading the same fragment a second time, and some sentences repeated themselves more times within the text of the novel. I can't point out those sentences because I didn't write them down, but I'm sure I'm right".
Adrian is convinced Laura is right. In order to solve this problem, he wants to identify the sequences of characters that are repeated in the text and to locate their positions.

Task

Identify for Adrian the maximum length character sequence repeated at least K times in the novel's text.

Input Data

File novel.in contains on the first line the positive integer K. The following lines beginning with line two, contain the text of the novel.

Output Data

File novel.out will contain on the first line two positive integers L and N, separated by a single space, representing the maximum length of the sequence that is repeated at least K times and respectively the exact number of repetitions.
On the second line, separated by a single space, numbers I₀ I₁ ... I_N will be displayed, representing the start positions of each of the N + 1 identical sequences of length L.
Starting with line three, the maximum length character sequence repeating at least K times will be displayed. You should not print a newline character after the sequence.

Constraints and Mentions

1 <= the number of characters in the input file <= 30000
1 <= K, N <= 300
All characters, including non-graphic characters from the input file, are counted.
The sequence of characters that is repeated can include any of the characters in the file.
The position of each character is calculated in relation to the first character in the novel, which is located on position 0
The number of repetitions is counted commencing with the second appearance of the sequence in the text.
If the problem has multiple solutions, only the solution regarding the repeated sequence that is the smallest in lexicographical order will be displayed..
For the test data a solution always exists.

Example

novel.in	novel.out	Explanation
1 Now I feel, like I've been to heaven and back 100 times Every time I look in her eyes Yes, I feel, like I've been to heaven and back 100 times I look deep in her light brown eyes and I loved her Why, why, oh, me Why couldn't she see that I loved her so much God, I love to look in her eyes... And I feel, like I've been to heaven and back 100 times Yes, I feel...	53 2 3 90 296 I feel, like I've been to heaven and back 100 times	The maximum length character sequence that is repeated at least once has 53 characters and appears in the text three times, therefore it is repeated 2 times. It is: I feel, like I've been to heaven and back 100 times 3 90 and 296 are the positions of the first character of the sequence, in relation to the position of the first character, 'N', of the text. The first character in the sequence is ' ' and the last is newline.

Time limit: 1 second/test
Memory Limit: 2 MB, from which 1 MB for stack.

prof. Constantin Galatan
C.N. "Liviu Rebreanu" Bistriţa
tucu_galatan@yahoo.com