Chu kì của một chuỗi là một tiền tố có thể được sử dụng để tạo ra toàn bộ chuỗi bằng cách lặp lại tiền tố. Lần lặp lại cuối cùng có thể là một phần. Ví dụ, các chu kì của abcabca là abc, abcabc và abcabca.

Nhiệm vụ của bạn là tìm độ dài của tất cả các chu kì của một xâu được cho.

Input

• Dòng đầu vào duy nhất có một xâu độ dài \(n\) gồm các kí tự a - z.

Output

• In tìm độ dài của tất cả các chu kì theo thứ tự tăng dần.

Constraints

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

Example

abcabca

3 6 7