409054: GYM103427 M String Problem

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 $$$S$$$ $$$(1\leq |S|\leq 10^6)$$$, which consists of lowercase Latin letters, a to z.

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$$$.

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