Problem Description

This task was originally an interactive problem from ICPC Asia Pacific Championship 2026. For Hydro OJ, it has been converted into a normal output-checking problem.

You are given a lowercase string $S$ of length $n$. For an integer $k$ $(1 \le k \le n)$, let $S(k)$ denote the suffix of $S$ starting from the $k$-th character.

Your task is to output a permutation $(p_1,p_2,\ldots,p_n)$ of $(1,2,\ldots,n)$ such that

in lexicographical order.

Because all suffixes starting at different positions are distinct, the answer is unique.

Input Format

The input contains one line: a lowercase string $S$.

The special judge also supports the format n S, but the recommended data format is a single string line.

Output Format

Output $n$ integers $p_1,p_2,\ldots,p_n$, representing the starting positions of all suffixes in increasing lexicographical order.

For compatibility with the original interactive statement, the special judge also accepts the format:

answer p1 p2 ... pn

However, in this Hydro version, contestants should not output query operations.

Constraints

$S$ consists only of lowercase Latin letters a to z.

Sample

Input

icpc

Output

4 2 1 3

Explanation

For $S=\texttt{icpc}$, the suffixes are:

• $S(1)=\texttt{icpc}$
• $S(2)=\texttt{cpc}$
• $S(3)=\texttt{pc}$
• $S(4)=\texttt{c}$

Their lexicographical order is:

so one valid output is 4 2 1 3.