Problem Description

Given a string $s$. Each character is guaranteed to be a lowercase letter. For each position in $s$, you are required to find the number of palindromic substrings ending at that position.

The string has been encrypted, and except for the first character, all other characters need to be decrypted using the answer from the previous position.

Specifically, if the answer for the $i$-th position ($i \geq 1$) is $k$, and the ASCII code of the character read at the $(i+1)$-th position is $c$, then the actual ASCII code of the $(i+1)$-th character is $(c - 97 + k) \bmod 26 + 97$. All characters remain lowercase letters before and after encryption.

Input Format

A single line containing the encrypted string $s$.

Output Format

A single line containing $|s|$ integers. The $i$-th integer represents the number of palindromic substrings in the original string ending at the $i$-th character.

Sample Input and Output

Input Sample #1

debber

Output Sample #1

1 1 1 2 1 1

Input Sample #2

lwkvjfrphhgkfvzzyx

Output Sample #2

1 1 2 2 3 1 1 1 1 2 3 1 1 1 1 2 3 4

Input Sample #3

azzzyyzyyx

Output Sample #3

1 2 1 2 3 2 2 2 3 3

Notes

Sample Explanation

The three samples decode to:

• dfccgs;
• lxlxlisqiiingwaaaa;
• aabaabbaaa.

Data Range and Constraints

For $100\%$ of the data, $1 \leq |s| \leq 5 \times 10^5$.

见题面 Input 部分

见题面 Output 部分