Період рядка — це префікс, який можна використовувати для створення всього рядка шляхом повторення префікса. Останнє повторення може бути частковим.

Наприклад, періодами abcabca є abc, abcabc і abcabca .

Ваше завдання знайти всі довжини періодів рядка.

Обмеження

• \(1≤n≤10^6\)

Формат вхідних даних

Єдиний вхідний рядок містить рядок довжиною \(n\) із символів 'a'–'z'.

Формат вихідних даних

Вивести всі довжини періодів у порядку зростання.

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

abcabca

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

3 6 7