Let me hear your voice; tell me the stories of your journey—
The joyful moments, the painful ones, and the encounters etched in your heart.
Description
You are given a string $S$ of length $n$, indexed starting from $1$. Let $S(i, j)=S_iS_{i+1}\cdots S_j$ denote the substring of $S$ from its $i$-th character to its $j$-th character.
If a nonempty string $B$ is both a prefix and a suffix of a string $X$, and $|B|<|X|$, then $B$ is called a Border of $X$, where $|X|$ denotes the length of $X$.
Initially, you are at the substring $S(1, n)$. Each jump is performed as follows:
- Choose a substring $X$ of the substring you are currently at.
- Choose a Border $B$ of $X$ such that $2|B|\ge |X|$.
- Jump to the substring corresponding to either the prefix occurrence or the suffix occurrence of $B$ in $X$, at your choice.
For example, when $S$ is aabaaba and you are at $S(1, 7)$, you can choose $X=S(2, 7)=$ abaaba. Its Border aba has length exactly half of $|X|$, so you can jump to $S(2, 4)$ or $S(5, 7)$.
For each $1\le i\le n$, determine the maximum number of jumps you can make starting from $S(1, n)$ and ending at $S(i, i)$. If it is unreachable, the answer is $-1$. Making no jumps is allowed.
There are multiple test cases.
Input
The first line contains an integer $T$, the number of test cases.
The test cases follow in order. Each test case consists of one line containing the string $S$.
Output
For each test case, output one line containing $n$ integers. The $i$-th integer is the answer for $S(i, i)$ (if $S(i, i)$ is unreachable, output -1).
Examples
Input 1
5 abbababbab bbabbaabbabbaaabab babbaaaaabaabaaabaaba baabaabaabaacaabaabaabaacaabaabaabaac bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
Output 1
-1 2 2 -1 -1 -1 2 2 -1 -1 3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1 -1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1
Note
In the first test case, $S=$ abbababbab, and its prefix and suffix of length $5$ are both abbab. You can make two jumps as follows:
- First jump to $S(1, 5)$, then choose $S(2, 3)=$ bb and jump to $S(2, 2)$ or $S(3, 3)$.
- First jump to $S(6, 10)$, then choose $S(7, 8)=$ bb and jump to $S(7, 7)$ or $S(8, 8)$.
You can continue jumping only if your first jump reaches one of the two occurrences of abbab above, and the next jump can only reach a single character. Therefore, the maximum number of jumps for each of these four positions is $2$.
All other positions are unreachable by jumping, so their answers are $-1$.
Examples 2
See wind2.in and wind2.ans in the attachment. This example satisfies the constraints of subtask 3.
Examples 3
See wind3.in and wind3.ans in the attachment. This example satisfies the constraints of subtask 5.
Examples 4
See wind4.in and wind4.ans in the attachment. This example satisfies the constraints of subtask 6.
Examples 5
See wind5.in and wind5.ans in the attachment. This example satisfies the constraints of subtask 8.
Constraints
Appropriate subtask dependencies are enabled for this problem.
| Subtask | $n\le$ | $\sum n\le$ | Special property | Points |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | None | $5$ |
| $2$ | $500$ | $14$ | ||
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $21$ | |
| $4$ | $10^5$ | $10^5$ | $18$ | |
| $5$ | $2\times 10^5$ | $2\times 10^5$ | A | $15$ |
| $6$ | B | $13$ | ||
| $7$ | C | $2$ | ||
| $8$ | None | $12$ |
Special property A: There exists a nonempty string $P$ such that $S$ is a prefix of the infinitely repeating string $P^{\infty}$ and $|P|\le 10$.
Special property B: $S$ is generated randomly: each character of $S$ is chosen uniformly at random from an alphabet of size $\ge 2$.
Special property C: For all $1\le i<n$, $S_i\neq S_{i+1}$.
For all test cases, $1\le n\le 2\times 10^5$, and the sum of the string lengths over all test cases in a single test file satisfies $\sum n\le 2\times 10^5$. The string $S$ contains only lowercase English letters.