D. Balanced strings
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

We call a string balanced if all its characters (those which occur in it at least once) occur in it an equal number of times. For example, aaaaa, badcx, bbaaab are balanced strings. However, abacb isn't a balanced string.

Given a string, find its longest (continuous) balanced substring.

The substring we're looking for doesn't have to contain all characters which occur in the original string. For example, the correct answer for cbababac is the substring bababa.

Input

The input consists of a single string of lowercase letters of English alphabet. The string has length N and the characters are indexed from 0 to N - 1.

Output

Print a single line containing two space-separated integers: indices of the character by which the substring we're looking for starts and the one by which it ends. If there are multiple optimal solutions, find the one that starts the earliest.

Examples
Input
baab
Output
0 3
Input
baaab
Output
1 3
Input
cbababac
Output
1 6
Input
cbabadbabae
Output
1 4
Note

There are 10 sets of tests, in which the following restrictions hold:

Set(s) no.Length of inputSet of letters used
11 ≤ N ≤ 20[ab]
21 ≤ N ≤ 1000[ab]
3-41 ≤ N ≤ 1000[abcdefgh]
51 ≤ N ≤ 105[ab]
61 ≤ N ≤ 105[abc] (the optimal solution doesn't use all three)
71 ≤ N ≤ 105[abc]
8-101 ≤ N ≤ 5·104[abcde]