题目描述

我们将由两个相等的字符串连接而成的字符串称为偶字符串。例如，xyzxyz和aaaaaa是偶字符串，而ababab和xyzxy则不是。

对于一个非空字符串$S$，我们定义$f(S)$为通过在$S$的末尾添加一个或多个字符所能得到的最短偶字符串。例如，$f($abaaba$)=$abaababaab。可以证明，对于非空字符串$S$，$f(S)$是唯一确定的。

给定一个由小写英文字母组成的偶字符串$S$。对于小写英文字母表中的每个字母，找出其在$f^{10^{100}} (S)$的第$l$个字符到第$r$个字符之间的出现次数。

其中，$f^{10^{100}} (S)$表示将$f$应用于$S$ $10^{100}$次所得到的字符串。

约束条件

• $2 ≤ |S| ≤ 2 \times 10^5$
• $1 ≤ l ≤ r ≤ 10^{18}$
• $S$是一个由小写英文字母组成的偶字符串。
• $l$和$r$是整数。

输入

输入满足以下标准格式：

$S$ $l$ $r$

输出

以行为单位，输出$26$个整数，每个整数之间用一个空格隔开。第$i$个整数表示小写英文字母表中第$i$个字母在$f^{10^{100}} (S)$的第$l$个字符到第$r$个字符之间的出现次数。

示例输入1

abaaba
6 10

示例输出1

3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

由于$f($abaaba$)=$abaababaab，所以$f^{10^{100}}(S)$的前十个字符也是abaababaab。因此，第六到第十个字符是abaab。在这个字符串中，a出现了三次，b出现了两次，其他字母都没有出现，因此输出应该为$3$和$2$，然后后面跟着二十四个$0$。

示例输入2

xx
1 1000000000000000000

示例输出2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0

示例输入3

vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000

示例输出3

87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0