Chu kỳ phát tín hiệu

Bối cảnh và bài toán

Một thiết bị phát tín hiệu bằng cách lặp lại một mẫu từ đầu chuỗi. Ở lần lặp cuối, thiết bị có thể dừng giữa chừng khi phiên truyền kết thúc. Kỹ sư muốn biết những độ dài mẫu nào có thể sinh ra đúng chuỗi đã ghi nhận.

Yêu cầu

Tìm mọi độ dài p sao cho chuỗi được tạo bởi việc lặp tiền tố dài p, trong đó lần lặp cuối có thể chỉ dùng một phần.

Input

Một dòng chứa chuỗi s.

Output

In mọi độ dài chu kỳ theo thứ tự tăng dần.

Ràng buộc

• 1 <= |s| <= 10^6
• s chỉ gồm chữ cái thường a..z.

Chấm điểm

Ví dụ 1

Input

abcabca

Output

3 6 7

Giải thích. Mẫu dài 3 là abc; lặp abcabc... sinh ra 7 ký tự đầu đúng bằng chuỗi. Độ dài 6 và 7 cũng hợp lệ.

Ví dụ 2

Input

aaaa

Output

1 2 3 4

Giải thích. Mọi tiền tố của chuỗi toàn ký tự a đều có thể sinh chuỗi khi cho phép lần lặp cuối không đầy đủ.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: CSES Problem Set – Finding Periods – Finding Periods (1733).