Micro is having a string S made of lowercase English alphabets. He wants to find out the index where the suffix having rank i starts, $1 \le i \le |S|$. Help Micro with this.

Input:
The only line of input consists of a string.

Output:
Print N space separated integers, where $i^{th}$ integer denotes the index where the suffix having rank i starts

Constraints:
$1 \le |S| \le 10000$