Problem F. Fixed step

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Let us consider a character sequence S consisting of digits and lowercase Latin letters.

It is required to find a subsequence of S that has maximal length and consists of same character located at positions with a fixed step (that is, on equidistant positions).

If there are several solutions, choose any of them with the maximum step.

Input format

Input contains a single string S.

Output format

Output must contain index of the start position and step. Positions are numbered from zero.

If the subsequence has only one element, step must be zero.

Constraints

0 < |S| ≤ 5000

Sample tests

No. Standard input Standard output
1
ababbbabab1b2b2b3baa
1 2
2
abc123xyz456def789pt
0 0

0.109s 0.015s 13