题目描述

小猫的名气非常大，许多夫妇不辞辛劳地来到Byteland，请求小猫为他们刚出生的宝宝取名。他们不仅想要名字，还想借此出名。为了摆脱这种无聊的工作，聪明的小猫想出了一个简单但巧妙的算法：

步骤1：将父亲的名字和母亲的名字连接成一个新字符串$S$。

步骤2：找出$S$的所有合适的前缀-后缀字符串（即既是$S$的前缀，又是$S$的后缀的子串）。

示例：父亲的名字是'ala'，母亲的名字是'la'，则$S$='ala'+'la'='alala'。$S$可能的前缀-后缀字符串有{'a', 'ala', 'alala'}。给定字符串$S$，你能帮小猫编写一个程序，计算所有可能的前缀-后缀字符串的长度吗？（小猫可能会通过给你的宝宝取名来感谢你哦~）

输入格式

输入包含多个测试用例。每个测试用例单独一行，包含上述描述的字符串$S$。

限制条件：输入中仅包含小写字母，$1 \leq S的长度 \leq 400000$。

输出格式

对于每个测试用例，按升序输出一行整数，表示所有可能的前缀-后缀字符串的长度。

示例输入与输出

输入数据 1

ababcababababcabab
aaaaa

输出数据 1

2 4 9 18
1 2 3 4 5

来源

POJ Monthly--2006.01.22, Zeyuan Zhu