Дана строка, требуется построить суффиксный массив для этой строки. Суффиксный массив - лексикографически отсортированный массив всех суффиксов строки. Каждый суффикс задается целым числом — позицией начала.

Строка s лексикографически меньше строки t, если существует такое i, что si < ti и sj = tj для всех j < i. Или, если такого i не существует и строка s короче строки t.

Здесь si - код i-го символа строки s.

Входные данные

Одна строка - английский литературный текст. Длина текста не превосходит 105. Коды всех символов в тексте от 32 до 127.

Выходные данные

Выведите n чисел - суффиксный массив данной строки.