Stammering Aliens#1260
Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far, because, as luck would have it, they have stumbled upon a race of stammering aliens! Her team has discovered that, in every sufficiently long message, the most important words repeat a certain number of times as consecutive sequences of characters, even in the middle of other words. Moreover, sometimes they use contractions in an obscure way. For example, if they need to say "bab" twice, they might just send the message "babab", which is abbreviated since the second "b" of the first word can be used as the first "b" of the second word.
Thus, the message may contain overlapping repetitions of the same words again and again. As a result, Ellie turns to you, S.R. Hadden, for help in determining the essence of the message.
Given an integer and a string representing the message, your task is to find the longest substring of that appears at least times. For example, in the message , the length- word appears times, namely at positions , , and (where indices start at zero). No substring appearing or more times is longer (see the first example from the sample input). On the other hand, no substring appears or more times (see example ).
If there are several solutions, the substring with the rightmost occurrence has priority (see example ).
The input contains several test cases. Each test case consists of a line with an integer (m \ge 1), the minimum number of repetitions, followed by a line containing a string of length between and , inclusive. All characters in are lowercase letters from to . The last test case is denoted by m = 0 and must not be processed.
For each test case print one line. If there is no solution, output none; otherwise, print two integers in a line separated by a space. The first integer denotes the maximum length of a substring appearing at least times; the second integer is the rightmost starting position of this substring.
Example 1