Bajtazar wants to place a long inscription on his house. He decided to first order a suitable stencil with cut-out letters. He will then apply this stencil to the wall in the appropriate places and paint over it, resulting in the letters from the stencil appearing on the wall. When Bajtazar applies the stencil to the wall, he always paints all the letters on it. Bajtazar allows for the possibility that some letters on the wall might be painted multiple times as a result of different applications of the stencil, but the same letter must always be painted in each position (otherwise, the letters would overlap and the inscription would not be formed). The letters on the stencil are placed next to each other (there are no gaps).

The company from which Bajtazar buys the stencils has now launched a very attractive promotion: when ordering a stencil with a cut-out inscription, one also receives a second stencil with the same inscription, but cut out in reverse (from right to left). For example, if Bajtazar orders a stencil with the inscription olimpiada, he will receive stencils with the inscriptions olimpiada and adaipmilo.

Bajtazar is interested in all possibilities of ordering a stencil (with the free one) that will allow him to place his chosen inscription on his house. More precisely, he wants to know all possible lengths of stencils that he could order for this purpose. Help him!

Input

The first and only line of input contains a single word consisting of one to $1\,000\,000$ lowercase English letters: the inscription that Bajtazar wants to paint on his house. Let $n$ denote the length of this inscription.

Output

In the first and only line of output, print all possible stencil lengths sorted in ascending order, separated by single spaces.

Even if there is more than one valid stencil of a given length, its length should be printed only once.

Examples

Input 1

abcabcabacbabcab

Output 1

5 16

Note

Bajtazar could order a stencil abcab. He would then receive a free stencil bacba. The arrows show which stencil (ordered or free) should be applied to the wall to obtain the inscription from the input:

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

Evaluation

The test cases are divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.