[ARC077F] SS

题面翻译

Description

如果某个串可以由两个一样的串前后连接得到，我们就称之为“偶串”。比如说“xyzxyz”和“aaaaaa”是偶串，而“ababab”和“xyzxy”则不是偶串。

对于一个非空串S，我们定义f(S)是在S后面添加一些字符得到的最短偶串。比如f('abaaba')='abaababaab'。容易证明，对于一个非空串S，f(S)是唯一的

现在给定一个由小写英文字母构成的偶串S，你需要求出 $f^{10^{100}}(S)$ ，并统计计算结果的第l个字符到第r个字符中，每个字母出现了多少次

其中， $f^{10^{100}}$ 是指 $f(f(f(...f(S)...)))$ ，式子中共有 $10^{100}$ 个 $f$

Input

第一行输入串S

第二行两个数l,r

Output

对于每个字母，输出一个数字表示答案，两个数字之间应有一个空格

样例 #1

样例输入 #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

样例 #2

样例输入 #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

样例输入 #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

提示

制約

• $2\ \leq\ |S|\ \leq\ 2\times\ 10^5$
• $1\ \leq\ l\ \leq\ r\ \leq\ 10^{18}$