JB hates solving string problems. Therefore, when his friend Potato gives him a string problem to solve, he immediately gives it to you and continues playing Genshin Impact, the greatest game in the world.

You are given a string and then for each nonempty prefix, you need to find the largest substring in lexicographical order and point out the leftmost occurrence of the largest substring.

The only line contains a string  , which consists of lowercase Latin letters, 'a' to 'z'.

Output  lines, the -th of which contains two integers  and , indicating the leftmost occurrence of the largest substring in the prefix of length .

potato

1 1
1 2
3 3
3 4
3 5
5 6

pbpbppb

1 1
1 2
1 3
1 4
1 5
5 6
5 7