Chu kỳ của một xâu \(S\) được định nghĩa là xâu tiền tố của xâu \(S\) sao cho việc lặp lại nó một số lần nhất định sẽ tạo ra được xâu \(S\), lần lặp cuối cùng có thể chỉ giữ một phần đầu trong chu kỳ.

Ví dụ xâu pdfpdfp có các chu kỳ là pdf, pdfpdf, và pdfpdfp.

Yêu cầu: Tìm tất cả các chu kỳ với độ dài bất kỳ của xâu nhập vào.

Input

• Chứa một xâu ký tự \(S\) gồm các chữ cái từ a đến z.

Output

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

Ràng buộc

• \(|S|\leq10^6\).

Ví dụ

Sample input

pdfpdfp

Sample output

3 6 7