题目描述

小 Z 想要用一个文字图案装饰他的围墙，文字图案用长为 $n$ 的字符串 $S$ 表示。为了达到目的，他决定订购一个镂空模板，然后用喷漆喷出该图案。喷涂的时候模板不能翻转、旋转，不能只喷涂一部分，但是在喷涂的时候可以与之前相同字符的区域重合。例如，不可以用模板 b 喷出 p 或 q，不可以用模板 ab 喷出 a，但是可以用模板 abab 喷两次喷出 ababab。

订购时供应商表示，如果订购字符串 $T$，那么不仅可以获得字符串 $T$ 的模板，还可以获得其反串的模板（字符串的反串定义为，从右往左依次取出字符得到的字符串，例如，abc 的反串是 cba）。

小 Z 只想订购一个字符串 $T$，从而获得两个模板。他想要知道有哪些字符串 $T$ 满足，他能够用得到的两个模板喷出字符串 $S$。由于输出可能太大，他只想知道字符串 $T$ 的长度 $|T|$ 组成的集合。

输入格式

从文件 sza.in 中读入数据。

一行给出字符串 $S$。

输出格式

输出到文件 sza.out 中。

输出共一行，从小到大输出所有可能的长度，用空格分隔。

样例 1 输入

abcabcabacbabcab

样例 1 输出

5 16

样例 1 解释

可以选择长为 $5$ 的字符串 bacba，得到 bacba、abcab 两个模板，可以证明这是可行的；可以选择长为 $16$ 的字符串 abcabcabacbabcab 即 $S$，显然可以。可以证明剩下的长度均不合法。

样例 2

见选手目录下的 sza2.in 与 sza2.ans。

该样例满足 $n=201$，字符串 $S$ 为 $\texttt{a}^{100}\texttt{ba}^{100}$（其中 $T^k$ 表示字符串 $T$ 重复 $k$ 次并拼接所得到的字符串），答案为 $101,102,103,\cdots,201$。

样例 3

见选手目录下的 sza3.in 与 sza3.ans。

该样例满足 $n=50000$，字符串 $S$ 为 $(\texttt{ab})^{25000}$，答案为 $2,4,6,\cdots,50000$。

样例 4

见选手目录下的 sza4.in 与 sza4.ans。

该样例满足子任务 $2$ 的限制。

样例 5

见选手目录下的 sza5.in 与 sza5.ans。

该样例满足子任务 $3$ 的限制。

样例 6

见选手目录下的 sza6.in 与 sza6.ans。

该样例满足子任务 $4$ 的限制。

数据范围

对于所有测试数据，保证：$1\le n\le10^6$，$S$ 的字符集为小写英文字母。

本题评测方式为：捆绑，某个子任务的分数被计入当且仅当该子任务内所有测试点均通过。