题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Szablon 2

Bajtazar 想在自家墙上写下一行长长的字。他决定先订做一个带有镂空字母的模板，然后将模板贴到墙上合适的位置，用喷漆涂抹，让墙上显现出模板上的字母。每次贴上模板，他都会涂满模板上的所有字母。他不介意某些字母被多次涂画（通过不同的模板位置），但每个位置的字母必须始终一致（否则字母叠加会毁了字迹）。模板上的字母是连续排列的，没有空隙。

Bajtazar 常去的模板供应商最近推出了一项超值优惠：订购一个镂空文字模板，就会免费附赠一个相同文字但反向镂空的模板（从右到左）。比如，如果他订购模板 olimpiada，就会收到 olimpiada 和 adaipmilo 两个模板。

Bajtazar 很好奇，想知道所有可能的模板订购方案（含赠品），让他能在墙上写出自己想要的文字。确切来说，他希望了解所有可能的模板长度。请你帮他解决这个问题！

输入格式

输入只有一行，包含一个由 $1$ 到 $1000000$ 个小写英文字母组成的单词，表示 Bajtazar 想写在墙上的文字。以下用 $n$ 表示这个单词的长度。

输出格式

输出一行，包含所有可能的模板长度，按升序排列，用单个空格分隔。即使某长度存在多个有效模板，也只需输出该长度一次。

样例 1

输入

abcabcabacbabcab

输出

5 16

解释
Bajtazar 可以订购模板 abcab，附赠模板为 bacba。通过合理摆放这两个模板，即可拼出输入的文字。箭头显示应该将哪个模板（订购的和附赠的）应用到墙上，以获得输入中的文字。

样例 2

见附加文件下 sza1ocen.in 和 sza1ocen.out。
该样例满足 $n=201$，文字为 $\texttt{a}^{100}\texttt{ba}^{100}$，模板长度为 $101, 102, 103, \ldots, 201$。

样例 3

见附加文件下 sza2ocen.in 和 sza2ocen.out。
该样例满足 $n=50000$，文字为 $(\texttt{ab})^{25000}$，模板长度为 $2, 4, 6, \ldots, 50000$。

数据范围与提示

详细子任务附加限制及分值如下表所示。