## Description:

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$$$$.

## Input:

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$$$$.

## Output:

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

## Sample Input:

abababa

## Sample Output:

7 0 0 0 3 0 0