Determining Potential Initial String Lengths

You are given a non-empty string S consisting of lowercase letters. It is known that S is a prefix of a final string produced by applying a number of flip operations on some unknown initial string R. The flip operation is defined as follows:

For a string \(R = r_1r_2\cdots r_{|R|}\), its flip is \( R \Vert \text{reverse}(r_1r_2\cdots r_{|R|-1}) \), that is, you append the reverse of the string formed by the first \(|R|-1\) characters of \(R\) to \(R\) itself.

For example:

• Flipping abcd produces abcdcba.
• Flipping qw twice produces qwqwq.
• A single-character string remains unchanged regardless of the number of flips.

Green started with an unknown non-empty string R (composed of lowercase letters) and performed several (possibly 0) flip operations. Afterwards, he presented a non-empty string S and stated that S is a prefix of the final string obtained after the flips.

Your task is to help Yazid determine all possible values of \(|R|\) (the length of the initial string) that do not exceed \(|S|\) such that there exists some number of flips (possibly more than one) and an appropriate initial string \(R\) of that length making S a prefix of the final string. (It is known that every integer greater than \(|S|\) is valid, so you only need to consider lengths \(\le |S|\).)

Note: The final string is constructed recursively. For example, if you denote \(f(R)= R\Vert\text{reverse}(r_1r_2\cdots r_{|R|-1})\), then after \(m\) flips the string will be \(f^m(R)\). Ultimately, the final string is entirely determined by \(R\), and the positions in the final string impose consistency constraints on the characters of \(R\). Your goal is to determine, for each candidate length \(k\) (with \(1 \le k \le |S|\)), whether there exists an appropriate string \(R\) of length \(k\) such that S is a prefix of some \(f^m(R)\) with a suitable \(m \ge 0\).

inputFormat

The input consists of a single line containing the non-empty string S (only lowercase letters).

outputFormat

Output all valid values of \(|R|\) (the length of the initial string), in increasing order, separated by a single space.

sample

a

1