Periodic Prefixes

Time limit2sMemory limit128 MB

Summary

For each prefix of a string, find the largest count n such that the prefix is some substring repeated n times, using prefix-function techniques.

Level: Medium6 of 10
Topics: String matching, String, Math
Solved: No attempts yet

Problem

Let (X)^n denote the string made by writing string X consecutively n times. Thus (ab)^3 is ababab.

A string Y is periodic if it can be represented as (X)^n for some string X and some integer n > 1. The string ab is not periodic, but abab is periodic because it can be written as (ab)^2.

You are given a string S consisting only of lowercase English letters. For every prefix of S with length i, determine whether that prefix is periodic. If a prefix has more than one valid representation, choose the representation with the largest repetition count n.

Write a program that outputs every possible pair (i, n).

Constraints:

2 <= |S| <= 1,000,000
S consists only of lowercase English letters.

Input

The first line contains the string S.

Output

In increasing order of i, output i and the maximum repetition count n for each qualifying prefix, one pair per line.

Examples1

Example 1
Input
```
aabaab
```
Expected output
```
2 2
6 2
```