Description

If a string $s$ satisfies:

• For a pair of numbers $(k,l)~(k\ge 1,l\ge 1)$.
• $s$ is formed by concatenating $k$ copies of a string $t$ of length $l$.

Then $s$ is called a $(k,l)\text{ - repeat}$ string.

For example, $s=\tt abaabaabaaba$ is a $(4,3)\text{ - repeat}$ string with $t=\tt aba$.

Given a string $u$ (containing only characters $\texttt a$ and $\texttt b$), you need to find a contiguous substring of $u$ that is a $(k,l)\text{ - repeat}$ string, such that $k$ is as large as possible.

For example, $u=\tt babb\underline{abaabaabaaba}b$, where the underlined part is a $(4,3)\text{ - repeat}$ string, and in this case $k$ is maximized.

Input Format

The first line contains an integer $n$, representing the length of $u$.

The next $n$ lines each contain one character ($\texttt a$ or $\texttt b$), describing the string.

Output Format

The first line contains a number $k$.

The second line contains a number $l$.

The third line contains a number $p$, representing the starting position of this $(k,l)\text{ - repeat}$ substring (positions start from $1$).

If there are multiple valid answers, output any one of them.

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

4
3
5

Hint

Constraints

For $100\%$ of the testdata, $1\le n\le 5\times 10^{4}$, $u_i\in\{\tt a,b\}$.

Notes

Translated from BalticOI 2004 Day2 A Repeats.

Special thanks to

Translated by ChatGPT 5