접두사 배열

접미사 배열(suffix array)은 어떤 문자열의 모든 접미사를 사전 순으로 정렬한 뒤, 정렬된 순서대로 각 접미사가 시작하는 인덱스를 적어 둔 배열이다. 문자열 'banana'를 예로 들면 다음과 같다.

1. 'banana'의 접미사는 banana, anana, nana, ana, na, a 여섯 개다.
2. 이 접미사를 사전 순으로 정렬하면 a, ana, anana, banana, na, nana 순이 된다.
3. 정렬된 순서대로 원래 문자열에서의 시작 인덱스를 적으면 5, 3, 1, 0, 4, 2 이다.

그래서 'banana'의 접미사 배열은 {5, 3, 1, 0, 4, 2}이다.

연세대학교 PS 동아리 모르고리즘의 회원 택희와 남규가 문자열 문제 하나를 함께 풀고 있었다. 다음은 그때 오간 대화의 일부다.

• 택희: 이거 그냥 suffix array 구해 놓고 풀면 되겠는데?
• 남규: suffix array면.. 접미사 배열 구해서 뒤집으면 되나?
• 택희: ??
• 남규: ??
• 택희: suffix가 접미사인데?
• 남규: 아 맞네.. 접두사로 착각했네.
• 택희: 근데 그러면 접두사 배열은 어떻게 구하지?
• 남규: 그러게?
• 택희: 문자열 뒤집고 suffix array 구하면 되나? 아닌데..?

두 사람은 그대로 혼란에 빠졌다. 혼란스러워하는 택희와 남규를 대신해 접두사 배열을 구하는 프로그램을 작성하자.

첫 줄에 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다. ($1 \le |S| \le 100000$)

$|S|$개의 줄에 걸쳐, $S$의 모든 접두사를 사전 순으로 정렬했을 때 목록의 첫 접두사부터 마지막 접두사까지 각 접두사가 끝나는 인덱스를 순서대로 출력한다. 문자열의 인덱스는 0부터 시작한다.