Description

Original problem from: POJ 2752

Given several strings (the total length of these strings is $\le 4\times 10^5$), for each string, find all the lengths of substrings that are both prefixes and suffixes.

For example: ababcababababcabab, the substrings that are both prefixes and suffixes are: ab, abab, ababcabab, ababcababababcabab.

Input Format

Input consists of several lines, each containing one string.

Output Format

For each string, output one line containing several increasing integers, representing the lengths of all substrings that are both prefixes and suffixes.

Sample 1

ababcababababcabab
aaaaa

2 4 9 18
1 2 3 4 5