Problem Description

Given a string $s$. It is guaranteed that each character is a lowercase letter. For each position in $s$, find the number of palindromic substrings that end at that position.

This string has been encrypted. Except for the first character, all other characters must be decrypted using the answer from the previous position.

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

Input Format

One line containing a string $s$, representing the encrypted string.

Output Format

One line with $|s|$ integers. The $i$-th integer represents the number of palindromic substrings in the original string that end at the $i$-th character.

debber

1 1 1 2 1 1

lwkvjfrphhgkfvzzyx

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

azzzyyzyyx

1 2 1 2 3 2 2 2 3 3

Hint

Sample Explanation

After decoding, the three samples are respectively:

• $\verb!dfccgs!$;
• $\verb!lxlxlisqiiingwaaaa!$;
• $\verb!aabaabbaaa!$.

Constraints and Notes

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

Translated by ChatGPT 5