764. Earn your freedom

0

Easy

You have been captured by Alexander the Great and he has given you a challenge to earn your freedom. Given a string s consisting of lowercase letters, the letters form consecutive groups of the same character. For example, in the string s = "cfxxxxzyy", the groups are "c", "f", "xxxx", "z", and "yy". A group is defined by an interval [start, end], where start and end represent the starting and ending indices (inclusive and 0-based) of the group. In the example above, the group "xxxx" has the interval [3,6]. A group is considered large if it contains 3 or more characters. Return the intervals of every large group, sorted in increasing order by the start index.

Input Format

The input consists of a string S.

Output Format

Each line of the output should contain two integers representing the start and end indices of a group.

Example

Input

cbbxxxxzzzd

Output

3 6 7 9

Constraints

1 <= s.length() <= 1000
The string s contains lowercase English letters only.