Các viền của mã phiên

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

Một giao thức truyền tin dùng cùng một đoạn đầu và đoạn cuối của mã phiên để kiểm tra tính liên tục. Một độ dài được coi là hợp lệ nếu tiền tố có độ dài đó cũng chính là hậu tố của toàn chuỗi, nhưng không được lấy toàn bộ chuỗi.

Yêu cầu

Liệt kê mọi độ dài k sao cho tiền tố độ dài k bằng hậu tố độ dài k và k < |s|.

Input

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

Output

In các độ dài hợp lệ theo thứ tự tăng dần, cách nhau bởi dấu cách. Nếu không có, in dòng trống.

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

abcababcab

Output

2 5

Giải thích. Các tiền tố ab và abcab đồng thời là hậu tố.

Ví dụ 2

Input

abcd

Output

Giải thích. Không có tiền tố khác toàn chuỗi đồng thời là hậu tố.

Thông tin bài tập

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