Суфіксний масив

Дано рядок, для якого потрібно побудувати суфіксний масив. Суфіксний масив — це лексикографічно відсортований масив усіх суфіксів рядка, де кожен суфікс представлений цілим числом, що вказує на позицію його початку.

Рядок s вважається лексикографічно меншим за рядок t, якщо існує таке i, що s[i] < t[i] і s[j] = t[j] для всіх j < i. Або, якщо такого i не існує, і рядок s коротший за рядок t.

Тут s[i] — це код i-го символу рядка s.

Вхідні дані

Один рядок — текст англійською мовою. Довжина тексту не перевищує 10^5. Коди всіх символів у тексті знаходяться в діапазоні від 32 до 127.

Вихідні дані

Виведіть n чисел — суфіксний масив для даного рядка.

Приклади