P5446 [THUPC 2018] Lvlvl and Skewers

Lvlvl and Yazid are good friends. They play a skewer game together.

Lvlvl has a non-empty string $R$ consisting of lowercase letters, but Yazid does not know what it is. We define the **flip** operation: flip-copy a string using its last character as the axis of symmetry. Formally, if the string to be flipped is $R$, then take the first $\left| R\right|-1$ characters, reverse them, and append them to the end of the string. For example, after applying the flip operation to `abcd`, we get `abcdcba`; if we apply the flip operation **$2$ times** in a row to `qw`, we get `qwqwq`; for `z`, no matter how many times we apply the flip operation, it will not change. The playful Lvlvl performed the flip operation several times (possibly $0$ times). Then the naughty Lvlvl showed a non-empty string $S$, and said that $S$ is a prefix of the **final** string $R$. Now he wants to test Yazid: what lengths could the **initial** string $R$ have? Yazid asked you, who are participating in the Tsinghua campus contest, to help solve this problem. But the clever Yazid noticed that every integer greater than $\left| S\right|$ must be a possible length of $R$, so you only need to tell him the possible lengths of $R$ that do not exceed $\left| S\right|$. To help you understand the problem, Yazid also explains some concepts and notation: - For a string $S$, $\left| S\right|$ denotes its length. - For a string $S$, we say that a string $T$ is its prefix if and only if $\left| T\right|\leq\left| S\right|$, and for every integer $i$ with $1\leq i\leq\left| T\right|$, the $i$-th character of $T$ from the left is the same as the $i$-th character of $S$ from the left. (Intuitively, $T$ appears at the beginning of $S$.) - For example: `abc` is a prefix of `abcdefg`; `aba` is **not** a prefix of `abba`; `z` is a prefix of `z`; the empty string is a prefix of any string.

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. Each test case is described as follows: - One line contains a non-empty string $S$ consisting only of lowercase letters.

For each test case, output one line: - Output all possible values of $\left| R\right|$ that do not exceed $\left| S\right|$, in increasing order, separated by a single space.

### Constraints It is guaranteed that $\left| S\right|\leq 10^6$ and $\sum\left| S\right|\leq 5\times 10^6$. $\sum\left| S\right|$ denotes the total length $\left| S\right|$ of all test cases in a single test point. ### Notes - The input size is large, so please pay attention to input efficiency. - What does the last string in the sample mean? ### Copyright Information From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to [Pony.ai](http://pony.ai/) for supporting this contest. Resources such as the editorial can be found at . Translated by ChatGPT 5