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

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

一行一个字符串 $s$ 表示被加密后的串。

一行， $|s|$ 个整数。第 $i$ 个整数表示原串以第 $i$ 个字符结尾的回文子串个数。

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

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