Границя рядка — це префікс, який також є суфіксом рядка, але не весь рядок.

Наприклад, границя abcababcab - це ab і abcab.

Ваше завдання полягає в тому, щоб знайти всі довжини границь даного рядка.

Обмеження

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

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

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

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

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

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

abcababcab

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

2 5