반복

문자열 $s$가 $(k, l)$-반복이라는 것은, 길이 $l \ge 1$인 어떤 씨앗 문자열 $t$를 $k \ge 1$번 이어 붙여 $s$를 얻을 수 있다는 뜻이다. 예를 들어 문자열

s = abaabaabaaba

는 씨앗 문자열

t = aba

를 가진 $(4,3)$-반복이다. 즉 씨앗 문자열 $t$의 길이는 3이고, 전체 문자열 $s$는 $t$를 4번 반복해 얻는다.

다음 작업을 수행하는 프로그램을 작성하라. 입력으로 ‘a’와 ‘b’로만 이루어진 긴 문자열 $u$가 주어진다. 프로그램은 $u$의 부분 문자열로 등장하는 $(k,l)$-반복 중에서 $k$가 최대인 것을 찾아야 한다. 예를 들어 입력 문자열

u = babbabaabaabaabab

에는 5번 위치에서 시작하는 $(4,3)$-반복 $s$가 있다. $u$에 4번보다 더 많이 반복되는 연속 부분 문자열이 없으므로, 프로그램은 이 부분 문자열을 출력해야 한다.

첫째 줄에 입력 문자열의 길이 $n$이 주어진다 ($1 \le n \le 50000$).

다음 $n$개 줄에 입력 문자열이 한 줄에 한 문자씩 (‘a’ 또는 ‘b’) 순서대로 주어진다.

출력은 세 정수로 이루어지며, 각각을 한 줄에 출력한다. 이 정수들은 프로그램이 찾은 $(k, l)$-반복을 다음과 같이 나타낸다.

1. 첫째 줄에는 최대화한 반복 횟수 $k$를 출력한다.
2. 둘째 줄에는 $k$번 반복되는 씨앗 문자열의 길이 $l$을 출력한다.
3. 셋째 줄에는 $(k, l)$-반복이 시작하는 위치 $p$를 출력한다 ($1 \le p \le n$).

주어진 입력에 대해 $k$가 같은 답이 여러 개라면 그중 아무거나 출력해도 된다.

입력 문자열의 5번째 문자(입력의 6번째 줄)에서 시작하는 $(4, 3)$-반복이 존재한다.