Дано рядок. Потрібно побудувати суфіксний масив для цього рядка. Суфіксний масив - лексикографічно відсортований масив усіх суфіксів рядка. Кожен суфікс задається цілим числом – позицією початку.

Рядок \(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\) чисел - суфіксний масив цього рядка.

Приклад вхідних даних

99 bottles of beer.

Приклад вихідних даних

14 3 11 19 2 1 15 4 16 17 9 13 8 12 5 18 10 7 6