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

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

Input

• Dòng đầu vào duy nhất có một xâu độ dài \(n\) gồm các kí tự a - z.

Output

• In độ dài của tất cả biên theo thứ tự tăng dần.

Constraints

• \(1 \leq n \leq 10^6\)

Example