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 ~\texttt{babb} \underline{\texttt{abaabaabaaba}} \texttt{b}~ shows the ~(4,3)~-repeat. No substring of ~u~ has more than ~4~ repeats.