Stammering Aliens

Time limit1sMemory limit128 MB

Summary

Given a string and a minimum repeat count m, find the longest substring occurring at least m times (overlaps allowed), breaking ties by rightmost starting position, using suffix array or suffix automaton techniques.

Level: Hard8 of 10
Topics: String matching, Binary search, String
Solved: No attempts yet

Problem

Dr. Ellie Arroway has made contact with an extraterrestrial civilization. Every attempt to decode their messages has failed so far because, as luck would have it, the aliens turned out to be a stuttering race. Her team discovered that in every sufficiently long message the most important words appear repeated several times as sequences of consecutive characters, even in the middle of other words. Moreover, the aliens sometimes contract their speech in an obscure way. For instance, if they need to say bab twice, they may send the message babab, reusing the second b of the first word as the first b of the second one.

Thus a message can contain possibly overlapping repetitions of the same word over and over again. Your task is the following.

Given an integer $m$ and a string $s$ representing the message, find the length of the longest substring of $s$ that appears at least $m$ times. Overlapping occurrences are all counted. For example, in the message baaaababababbababbab the length-5 word babab occurs 3 times, at positions 5, 7 and 12 (indices start at zero); no substring occurring 3 or more times is longer. On the other hand, no substring of this message occurs 11 or more times.

If several longest substrings exist, prefer the one whose occurrence is rightmost (largest starting position).

Input

The input contains several test cases. Each test case consists of a line with an integer $m$ ( $m \ge 1$ ), the minimum number of repetitions, followed by a line containing a string $s$ whose length is between $m$ and $40\,000$ , inclusive. All characters of $s$ are lowercase letters from a to z. The last test case is denoted by $m = 0$ and must not be processed.

Output

Print one line for each test case. If there is no solution, print none. Otherwise print two integers separated by a space: the first is the maximum length of a substring appearing at least $m$ times, and the second is the rightmost starting position (0-indexed) of such a substring.

Examples7

Example 1

Input

3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

Expected output

5 12
none
4 2

Example 2

Input

1
abc
2
aa
2
banana
3
aaaa
0

Expected output

Example 3
Input
```
5
abcde
2
zzzzz
0
```
Expected output
```
none
4 1
```

Example 4

Input

2
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
0

Expected output

99 1

Example 5
Input
```
2
aabbaabb
0
```
Expected output
```
4 4
```
Example 6
Input
```
1
mississippi
0
```
Expected output
```
11 0
```
Example 7
Input
```
2
baaaababababbababbab
0
```
Expected output
```
8 12
```