접미사 배열 2

문자열 $S$의 접미사 배열은 $S$의 모든 접미사를 사전순으로 정렬한 배열이다.

banana의 접미사는 banana, anana, nana, ana, na, a로 모두 6개이고, 사전순으로 정렬하면 a, ana, anana, banana, na, nana가 된다.

각 접미사는 시작하는 문자의 위치로 번호를 매긴다. 위치는 0부터 세므로 banana는 0번 접미사, ana는 3번 접미사이다.

문자열 $S$가 주어지면 모든 접미사를 사전순으로 정렬한 다음 접미사 번호를 차례대로 출력하는 프로그램을 작성하시오.

첫째 줄에 문자열 $S$가 주어진다. $S$는 알파벳 소문자로만 이루어져 있고, 길이는 1 이상 100,000 이하이다.

접미사를 사전순으로 정렬한 순서대로, 접미사 번호를 한 줄에 하나씩 출력한다.

$S$가 abcdabcabb이면 정렬한 접미사와 그 번호는 다음과 같다.

• 7: abb
• 4: abcabb
• 0: abcdabcabb
• 9: b
• 8: bb
• 5: bcabb
• 1: bcdabcabb
• 6: cabb
• 2: cdabcabb
• 3: dabcabb