크기 N 인 문자열 S ( 소문자로 구성 ) 가 주어질 때 이 문자열의 접두어(prefix)가 주기를 가지는 문자인지를 알고자 한다.

A 가 K 번 연결되어 있을 때 크기 i 인 접두어 S 를 AK 로 쓸 수 있다. 물론 우리는 주기 K 또한 알고자 한다.

입력

• 첫 줄에는 문자열의 크기를 나타내는 N 이 주어진다. 2 <= N <= 1 000 000
• 두 번째 줄에는 문자열이 주어진다.

출력

입출력 예

입력

3
aaa

출력

2 2
3 3

입력

12
aabaabaabaab

출력

2 2
6 2
9 3
12 4

출처: Southeastern Europe 2004