题目描述

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

对于非空字符串 $S$，定义 $f(S)$ 为“在 $S$ 后追加若干（至少 $1$ 个）字符后得到的所有偶字符串中长度最短的一个”。例如，$f($abaaba$)=$abaababaab。可以证明，对于任意非空字符串，这样的字符串仅有唯一一个。

给定一个仅包含小写英文字母的偶字符串 $S$。请你计算 $f^{10^{100}}\ (S)$ 的第 $l$ 个字母到第 $r$ 个字母之间，各个小写英文字母出现的次数。

这里 $f^{10^{100}}(S)$ 表示对 $S$ 连续应用 $f$ 操作 $10^{100}$ 次所得的字符串，即 $S$ 经过 $10^{100}$ 次 $f$ 变换后的字符串。

输入格式

输入由一行组成，包含：

$S$ $l$ $r$

输出格式

请输出 $26$ 个用空格分隔的整数，第 $i$ 个表示 $f^{10^{100}}(S)$ 的第 $l$ 个字母到第 $r$ 个字母之间，第 $i$ 个英文字母在这段区间中出现的次数。

样例 1

输入

abaaba
6 10

输出

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

样例 2

输入

xx
1 1000000000000000000

输出

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

输出

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

说明/提示

限制条件

• $2 \leq |S| \leq 2 \times 10^5$
• $1 \leq l \leq r \leq 10^{18}$
• $S$ 仅由小写英文字母组成、且是偶字符串。
• $l,r$ 均为整数。

样例解释 1

$f($abaaba$)=$abaababaab，因此 $f^{10^{100}}(S)$ 的前 $10$ 个字符也就是 abaababaab。所以第 $6$ 到第 $10$ 个字符是 abaab。在 abaab 中，a 出现了 $3$ 次，b 出现了 $2$ 次，`c$至$z$ 都未出现，所以输出 $1$ 号为 $3$，$2$ 号为 $2$，其余 $24$ 个均为 $0$。

由 ChatGPT 5 翻译