This is a template problem.

Read a string of length $n$ consisting of uppercase letters, lowercase letters, or digits. Sort all non-empty suffixes of this string in lexicographical order, and output the starting positions of these suffixes in the original string in order. The positions are numbered from $1$ to $n$.

Input

A single line containing a string of length $n$ consisting only of uppercase letters, lowercase letters, or digits.

Output

A single line containing $n$ integers, where the $i$-th integer is $\text{SA}[i]$.

Subtasks

Subtask 1 (25 points), $1 \leq n \leq 10^3$

Subtask 2 (25 points), $1 \leq n \leq 10^4$

Subtask 3 (25 points), $1 \leq n \leq 10^5$

Subtask 4 (25 points), $1 \leq n \leq 10^6$

Examples

Input 1

ababa

Output 1

5 3 1 4 2

Input 2

0103210002010200210200101020202222010111

Output 2

7 21 8 15 22 35 11 24 1 37 19 13 9 26 28 16 30 3 40 6 23 36 18 12 25 2 39 38 20 14 34 10 27 29 5 17 33 32 31 4