Given a string $a$ of length $n$ consisting of lowercase letters, let the $i$-th character be $a_i$ ($1 \le i \le n$).
Let $s_i$ be the string obtained by deleting the $i$-th character from $a$. Sort $s_1, s_2, \dots, s_n$ in lexicographical order. If two strings are equal, the one with the smaller index is considered lexicographically smaller.
Input
The first line contains an integer $n$.
The second line contains a string $a$ of length $n$ consisting of lowercase letters.
Output
Output $n$ integers $k_1, k_2, \dots, k_n$ separated by spaces, representing the order such that $s_{k_1} < s_{k_2} < \dots < s_{k_n}$.
Examples
Input 1
7 aabaaab
Output 1
3 7 4 5 6 1 2
Note
$$ \begin{align} s_1 = s_2 & = abaaab \nonumber \\ s_3 & = aaaaab \nonumber \\ s_4 = s_5 = s_6 & = aabaab \nonumber \\ s_7 & = aabaaa \nonumber \end{align} $$
Subtasks
For all test cases, $1 \le n \le 10^6$.
- For $10\%$ of the data, $1 \le n \le 2000$;
- For another $20\%$ of the data, $1 \le n \le 10^5$ and no two adjacent characters $a_i, a_{i+1}$ are equal;
- For another $30\%$ of the data, $1 \le n \le 10^5$;
- For the remaining $40\%$ of the data, there are no special restrictions.