题目描述

一段密码串 $s$ 只由小写字母组成，长度为 $n$。

如果 $s$ 的某段前缀和某段后缀完全相同（两段长度相同、可以互相重合，但不能把整个串完全覆盖住），就把这个长度称为一个「呼应」。

请按长度从小到大输出所有呼应长度。

输入格式

一行一个字符串 $s$。

输出格式

一行，按升序输出所有呼应长度，用空格分隔。如果不存在任何呼应，输出 0。

输入输出样例 #1

输入 #1

abacaba

输出 #1

1 3

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^6$，字符串只含小写字母。

样例说明：长度为 $1$ 的前缀 a 与后缀 a 相同；长度为 $3$ 的前缀 aba 与后缀 aba 相同，所以答案是 1 3。