Repeats

A string $s$ is called a $(k, l)$-repeat if $s$ is obtained by concatenating $k \ge 1$ copies of some seed string $t$ of length $l \ge 1$. For example, the string

s = abaabaabaaba

is a $(4,3)$-repeat with seed string

t = aba

That is, the seed string $t$ has length 3, and the whole string $s$ is obtained by repeating $t$ four times.

Write a program for the following task. The input is a long string $u$ consisting of the characters ‘a’ and ‘b’. The program must find a $(k,l)$-repeat that occurs as a substring of $u$ with $k$ as large as possible. For example, the input string

u = babbabaabaabaabab

contains the $(4,3)$-repeat $s$ starting at position 5. Since $u$ contains no other contiguous substring with more than 4 repeats, the program must output this substring.

The first line contains one integer, the length $n$ of the input string ($1 \le n \le 50000$).

The next $n$ lines contain the input string, one character (‘a’ or ‘b’) per line, in order.

The output consists of three integers, each on its own line. They report the $(k, l)$-repeat your program found as follows.

1. The first line contains the repeat count $k$ that is maximized.
2. The second line contains the length $l$ of the seed string that is repeated $k$ times.
3. The third and final line contains the position $p$ at which the $(k, l)$-repeat starts ($1 \le p \le n$).

If the given input has several answers with the same $k$, your program may report any one of them.

A $(4, 3)$-repeat starts at the 5th character of the input string (line 6 of the input).