M. String Problem
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

The only line contains a string $$$S$$$ $$$(1\leq |S|\leq 10^6)$$$, which consists of lowercase Latin letters, a to z.

Output

Output $$$|S|$$$ lines, the $$$i$$$-th of which contains two integers $$$l_i$$$ and $$$r_i$$$, indicating the leftmost occurrence of the largest substring in the prefix of length $$$i$$$.

Examples
Input
potato
Output
1 1
1 2
3 3
3 4
3 5
5 6
Input
pbpbppb
Output
1 1
1 2
1 3
1 4
1 5
5 6
5 7