P5496 [Template] Palindromic Tree / Palindromic Automaton (PAM).

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.

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

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.

### 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