P401927 - GYM100584 D Balanced strings - SSOJ - 省实信息奥赛评测系统

Memory Limit：256 MB Time Limit：1 S

Judge Style：Text Compare Creator：

Submit：0 Solved：0

上一题 Submit 下一题 Submit Record Statistics MD

D. Balanced stringstime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput

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 input	Set of letters used
1	1 ≤ N ≤ 20	[ab]
2	1 ≤ N ≤ 1000	[ab]
3-4	1 ≤ N ≤ 1000	[abcdefgh]
5	1 ≤ N ≤ 10⁵	[ab]
6	1 ≤ N ≤ 10⁵	[abc] (the optimal solution doesn't use all three)
7	1 ≤ N ≤ 10⁵	[abc]
8-10	1 ≤ N ≤ 5·10⁴	[abcde]

Slovak OI, National round 2014

401927: GYM100584 D Balanced strings

Description

Source/Category

加入题单