Baltic Olympiad in Informatics: 2004 Day 2, Problem 1

A string $s$ is called a $(k,l)$-repeat if $s$ is obtained by concatenating $k\ge 1$ times some seed string $t$ with length $l\ge 1$. For example, the string abaabaabaaba is a $(4,3)$-repeat with aba as the seed string. That is, the seed string aba is $3$ characters long, and the whole string $s$ is obtained by repeating it $4$ times.

You are given a string $u$. Find one $(k,l)$-repeat $s$ that occurs as a substring within $u$ with a $k$ as large as possible.

Constraints

$1\le n\le 5\times {10}^4$

$u$ only consists of a or b.

Input Specification

The first line of input contains one integer $n$: the length of the input string $u$.

The next $n$ lines describe the string $u$. Each line contains one character (either a or b).

Output Specification

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

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

If there are multiple solutions with the same $k$, your program can output any one of them.

Sample Input

17
b
a
b
b
a
b
a
a
b
a
a
b
a
a
b
a
b

Sample Output

4
3
5

Sample Explanation

A $(4,3)$-repeat is found starting at the $5^{\text{th}}$ character of the input string (which is line $6$ of the input file).

The underlined substring $s$ of $\mathtt{\text{babb}}\underset{―}{\mathtt{\text{abaabaabaaba}}}\mathtt{\text{b}}$ shows the $(4,3)$-repeat. No substring of $u$ has more than $4$ repeats.