Description

给定若干长度小于等于400,000的字符串，在每个字符串中求出所有既是前缀又是后缀的子串长度。
例如：ababcababababcabab,既是前缀又是后缀的有：ab, abab, ababcabab, ababcababababcabab。

Format

Input

输入文件包含若干组测试数据，每行包含一个字符串S（字符串中只包含小写字母）。

Output

每个字符串对应一行输出。每行输出由若干个升序的整数组成。表示对应的字符串的子串的长度。

Sample 1

Input

ababcababababcabab
aaaaa

Output

2 4 9 18
1 2 3 4 5

Limitation

1s, 64MiB for each test case.

Source

poj2752