Description
A period of a string is a substring that can generate the entire string by repeating itself one or more times, possibly with a partial repetition at the end.
For example, in the string "abcabcabc", the substring "abc" is a period because the string can be formed by repeating "abc" three times: "abcabcabc" = "abc" + "abc" + "abc". And "abc" is also a period of "abca", since "abca" = "abc" + "a".
A string can have multiple periods of different lengths. Your task is to find all period lengths of a given string.
Input
The only input line has a string of length n consisting of characters a-z.
Restrictions
- 1 ≤ n ≤ 106
Subtask
for the first 3 test cases 1 ≤ n ≤ 1000
Output
Print all period lengths in increasing order.
Remember there is a space(' ') but no '\n' in the end
Hint:
