Bajtazar 想在他的房子上放置一个长字符串。他决定先订购一个带有镂空字母的模板。然后，他会将该模板放置在墙上的适当位置，并用油漆涂刷，从而在墙上显现出模板上的字母。当 Bajtazar 将模板贴在墙上时，他总是会涂刷模板上的所有字母。Bajtazar 允许墙上的某些字母通过多次放置模板而被重复涂刷，但每个位置涂刷的字母必须始终相同（否则字母会重叠，导致无法形成正确的字符串）。模板上的字母是紧密排列的（中间没有空隙）。

Bajtazar 订购模板的公司现在推出了一项非常有吸引力的促销活动：订购一个带有镂空字符串的模板时，还会免费赠送第二个模板，其内容与第一个相同，但顺序是反向的（从右到左）。例如，如果 Bajtazar 订购了一个镂空字符串为 olimpiada 的模板，他将获得字符串为 olimpiada 和 adaipmilo 的两个模板。

Bajtazar 对所有能够让他拼出目标字符串的模板订购方案（包括赠品）都感兴趣。更准确地说，他想知道所有可能的模板长度。请帮助他！

输入格式

输入的第一行也是唯一一行包含一个字符串，由 1 到 1,000,000 个小写英文字母组成：这是 Bajtazar 想要在墙上涂刷的字符串。设 $n$ 为该字符串的长度。

输出格式

在第一行输出所有可能的模板长度，按升序排列，并用空格分隔。

即使对于某个长度存在多个合法的模板，也只需输出该长度一次。

样例

输入 1

abcabcabacbabcab

输出 1

5 16

说明 1

Bajtazar 可以订购模板 abcab。这样他会免费获得模板 bacba。箭头显示了应该将哪个模板（订购的或赠送的）贴在墙上，以获得输入中的字符串：

a b c a b c a b a c b a b c a b

子任务