B-Suffix Array

题号：NC209429
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

The $B$ -function $B(t_1 t_2 \dots t_k) = b_1 b_2 \dots b_k$ of a string $t_1 t_2 \dots t_k$ is defined as follows.

If there is an index $j < i$ where $t_j = t_i$ , $b_i = \min_{1 \leq j < i, t_j = t_i}\{i - j\}$ ,
Otherwise, $b_i = 0$ .

Given a string $s_1 s_2 \dots s_n$ , sort its $n$ suffixes into increasing lexicographically order of the $B$ -function.

Formally, the task is to find a permutaion $p_1, p_2, \dots, p_n$ of $\{1, 2, \dots, n\}$ such that $B(s_{p_{i - 1}} \dots s_n) < B(s_{p_{i}} \dots s_n)$ holds for $i = 2, \dots, n$ .

输入描述:

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains a string .

* 
*  is either '`a`' or '`b`'.
* The sum of n does not exceed .

输出描述:

For each test case, print n integers which denote the result.

示例1

输入

复制

2
aa
3
aba
5
abaab

输出

复制

2 1
3 2 1
5 4 2 1 3

备注:

For s = aba, 
* 
* 
* 
Therefore, .