P5496 【模板】回文自动机（PAM）

给定一个字符串 $s$。保证每个字符为小写字母。对于 $s$ 的每个位置，请求出以该位置结尾的回文子串个数。 这个字符串被进行了加密，除了第一个字符，其他字符都需要通过上一个位置的答案来解密。 具体地，若第 $i(i\geq 1)$ 个位置的答案是 $k$，第 $i+1$ 个字符读入时的 $\rm ASCII$ 码为 $c$，则第 $i+1$ 个字符实际的 $\rm ASCII$ 码为 $(c-97+k)\bmod 26+97$。所有字符在加密前后都为小写字母。

无

无

### 样例解释 三个样例解码后分别为： - $\verb!dfccgs!$； - $\verb!lxlxlisqiiingwaaaa!$； - $\verb!aabaabbaaa!$。 ### 数据范围及约定 对于 $100\%$ 的数据， $1\leq |s|\leq 5\times 10^5$。