시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 6 5 2 100.000%

문제

어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다. 예를 들어 ab는 주기문이 아니지만, abab는 (ab)^2으로 표현할 수 있으므로 주기문이 된다.

문자열 S(2≤길이≤1,000,000)가 주어졌을 때, S의 앞에서부터 i개의 문자가 주기문의 형태가 되는 경우를 찾으려 한다. 가능한 경우가 여럿일 경우에는 n이 최대가 되는 경우를 구하려고 한다.

문자열 S가 주어졌을 때, 가능한 i, n 쌍을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다.

출력

i가 증가하는 순서대로, i, n 값을 한 줄에 하나씩 출력한다.

예제 입력

aabaab

예제 출력

2 2
6 2

힌트