Problem Description

The suffix array (SA) is an important data structure, usually implemented using the doubling method or the DC3 algorithm, which is beyond the scope of our discussion.

In this problem, we want to build a simple $O(n\log^2 n)$ method for constructing the suffix array using quicksort, hashing, and binary search.

More specifically, given a string $S$ of length $n$ (indexed from $0 \sim n-1$), we can use an integer $k(0 \le k < n)$ to represent the suffix $S(k \sim n-1)$ of $S$.

Sort all suffixes of $S$ in lexicographical order, and let the suffix with rank $i$ be denoted as SA[i].

In addition, for the suffix ranked $i$ and the suffix ranked $i-1$, let the length of their longest common prefix be denoted as Height[i]. In particular, define Height[0] = 0.

Your task is to output the two arrays SA and Height.

Input Format

Input a string whose length does not exceed $300000$.

The string consists of lowercase letters.

Output Format

The first line contains the array SA, where adjacent integers are separated by exactly $1$ space.

The second line contains the array Height, where adjacent integers are separated by exactly $1$ space.

ponoiiipoi

9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

Hint

Translated by ChatGPT 5