## SARRAY - Suffix Array

no tags

Given a string of length at most 100,000 consist of alphabets and numbers. Output the suffix array of the string.

A suffix array is an array of integers giving the starting positions (0-based) of suffixes of a string in lexicographical order. Consider a string "abracadabra0AbRa4Cad14abra". The size of the suffix array is equal to the length of the string. Below is the list of 26 suffixes of the string along with its starting position sorted in lexicographical order:

```POS SUFFIX
20 14abra
21 4abra
25 a
22 abra
23 bra
19 d14abra
24 ra
```

Note: this is a partial score problem.
O(n2 log(n)) is expected to score about 20-30. (Naive sorting all suffixes)
O(n log2(n)) is expected to score about 40. (OK for most programming contest problems)
O(n log n) is expected to score about 60-70. (Use counting sort for small alphabet size)
O(n) without tweaks is expected to score about 80-90.
O(n) with tweaks is expected to score 100. (This is meant for fun only :)

### Input

A single line containing the string.

### Output

The suffix array of the string.

### Example

```Input:

Output:
11
20
16
21
12
17
14
25
10
15
22
7
0
3
18
5
13
23
8
1
4
19
6
24
9
2
```