Sorted Deletion Strings

You are given a string a of length \( n \) consisting of lowercase letters. The \( i \)-th character is denoted by \( a_i \) for \( 1 \le i \le n \). For each index \( i \), let \( s_i \) be the string obtained by deleting the \( i \)-th character from a. Your task is to sort all strings \( s_1, s_2, \dots, s_n \) in lexicographical order. In the case that two strings are equal, the string with the smaller index \( i \) is considered lexicographically smaller.

After sorting, output the original indices corresponding to each \( s_i \) in the sorted order, separated by spaces.

inputFormat

The input consists of a single line containing the string a which is composed of lowercase English letters. The length \( n \) of the string satisfies \( 1 \le n \le 10^5 \) (or as specified by the problem constraints).

outputFormat

Output a single line with \( n \) integers separated by spaces. Each integer is an index from \( 1 \) to \( n \), representing the deletion operation whose resulting string is at that position in the lexicographical order.

sample

abc

3 2 1