题目描述

如果字符串 $s$ 满足：

• 对于一个数对 $(k,l)~(k\ge 1,l\ge 1)$。
• $s$ 是由 $k$ 个长度为 $l$ 的字符串 $t$ 拼接成的。

那么 $s$ 就被称作是一个 $(k,l)\text{ - repeat}$ 串。

如 $s=\tt abaabaabaaba$ 就是一个 $t=\tt aba$ 的 $(4,3)\text{ - repeat}$ 串。

对于一个字符串 $u$（仅含字符 $\texttt a$ 和 $\texttt b$），你需要找出其中的一段是 $(k,l)\text{ - repeat}$ 串的连续的字符串，使 $k$ 尽可能大。

例如 $u=\tt babb\underline{abaabaabaaba}b$，其中划线部分就是一个 $(4,3)\text{ - repeat}$ 串，这时 $k$ 的值最大。

输入格式

第一行一个整数 $n$，代表 $u$ 的长度。

接下来 $n$ 行，每行一个字符（$\texttt a$ 或 $\texttt b$），表示这个字符串。

输出格式

第一行一个数 $k$。

第二行一个数 $l$。

第三行一个数 $p$，表示这个 $(k,l)\text{ - repeat}$ 串的开始位置（位置从 $1$ 开始）。

如果有多种情况，输出任意一种。

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

4
3
5

提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 5\times 10^{4}$，$u_i\in\{\tt a,b\}$。

说明

译自 BalticOI 2004 Day2 A REPEATS

特别感谢