该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

你接到了上级的一个任务，需要帮助设计一个文本检测器，功能是检测冗余信息的位置。
冗余信息的位置是这样定义的：
假设文本为字符串S，如果从S的左端开始，连续读X个字符能组成的字符串Sx，从S的倒数第X个字符开始读X个字符至结束能组成字符串Sy，如果Sx=Sy，则判定为冗余信息，并且X即为冗余信息的位置。
举个例子，假设文本S为abcabc，那么冗余信息的位置为3（从S左端开始读3个字符为abc，而S的最后3个字符也为abc）
现在给你一个只包含小写字母的本文，请给出所有冗余信息的位置。

Format

Input

包含多组测试数据
对于每组测试数据，输入一行字符串，长度<=500000，且仅包含小写字母。

Output

对于每组测试数据输出一行，若干个数字，用空格隔开，表示该文本的所有冗余信息位置

Sample 1

Input

abcabc
aaaa
abba

Output

3 6
1 2 3 4
1 4

Limitation

1s, 128MB for each test case.

Hint

Source

Coolxxx