题目描述

给定一个字符串 $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$。