Một đường biên của một xâu là một tiền tố cũng đồng thời là hậu tố của xâu đó nhưng không phải toàn bộ xâu. Ví dụ, các đường biên của abcababcab là ab và abcab.

Nhiệm vụ của bạn là tìm tất cả độ dài đường biên của một xâu cho trước.

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~ gồm các ký tự a–z.

Kết quả

In ra tất cả độ dài đường biên của xâu theo thứ tự tăng dần.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

abcababcab

Kết quả:

2 5