Định nghĩa: Một chu kỳ (period) của một chuỗi là một tiền tố (prefix) có thể được lặp đi lặp lại để tạo thành toàn bộ chuỗi. Lần lặp cuối cùng có thể bị cắt ngắn.

Ví dụ: Với chuỗi abcabca:

Lấy tiền tố abc → lặp lại abc | abc | a → khớp với chuỗi → ✅ là chu kỳ.

Lấy tiền tố abcabc → lặp lại abcabc | a → khớp → ✅ là chu kỳ.

Lấy tiền tố abcabca → lặp lại 1 lần → ✅ là chu kỳ.

Do đó, các độ dài chu kỳ là: 3 6 7.

Nhiệm vụ

Cho một chuỗi s có độ dài n, hãy tìm tất cả các độ dài của các chu kỳ của chuỗi, theo thứ tự tăng dần.

Dữ liệu vào:

Dòng duy nhất chứa chuỗi s, độ dài n.

s chỉ gồm các ký tự thường a–z.

Dữ liệu ra:

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

Ràng buộc

1 ≤ n ≤ 10^6

Ví dụ :

Input:

abcabca

Output:

3 6 7