You are given a string $S = s_1s_2..s_{|S|}$ containing only lowercase English letters. For each integer $i \in [1, |S|]$ , please output how many substrings $s_ls_{l + 1}...s_r$ satisfy the following conditions:

$\quad$ $\bullet$ $r - l + 1$ equals to $i$.

$\quad$ $\bullet$ The substring $s_ls_{l + 1}...s_r$ is a palindrome string.

$\quad$ $\bullet$ $s_ls_{l + 1}...s_{ \lfloor (l + r) / 2 \rfloor }$ is a palindrome string too.

$|S|$ denotes the length of string $S$.

A palindrome string is a sequence of characters which reads the same backward as forward, such as $madam$ or $racecar$ or $abba$.

There are multiple test cases.

Each case starts with a line containing a string $S(1 \leq |S| \leq 3 \times 10^5)$ containing only lowercase English letters.

It is guaranteed that the sum of $|S|$ in all test cases is no larger than $4 \times 10^6$.

For each test case, output one line containing $|S|$ integers. Any two adjacent integers are separated by a space.