[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 对于每个字母，输出一个数字表示答案，两个数字之间应有一个空格

[problemUrl]: https://atcoder.jp/contests/arc077/tasks/arc077_d 同じ文字列を $ 2 $ つ並べてできる文字列のことを偶文字列と呼ぶことにします。 例えば、 `xyzxyz` や `aaaaaa` は偶文字列ですが、`ababab` や `xyzxy` は偶文字列ではありません。 空でない文字列 $ S $ に対して、$ f(S) $ を 「$ S $ の後ろに $ 1 $ 文字以上の文字を追加してできる偶文字列のうち 最短の文字列」として定義します。 例えば、 $ f( $`abaaba`$ )= $`abaababaab` です。 このような文字列は空でない文字列に対してはちょうど $ 1 $ 通りに定まることが証明できます。 アルファベットの小文字からなる偶文字列 $ S $ が与えられます。 $ f^{10^{100}}\ (S) $ の $ l $ 文字目から $ r $ 文字目までに アルファベットの小文字がそれぞれ何回出現するかを求めて下さい。 $ f^{10^{100}}\ (S) $ というのは、 $ f(f(f(\ ...\ f(S)\ ...\ ))) $ のように、$ S $ を $ 10^{100} $ 回 $ f $ で写した文字列のことを指します。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ l $ $ r $

$ 26 $ 個の整数を空白区切りで $ 1 $ 行に出力せよ。 $ i $ 番目には、 $ f^{10^{100}}(S) $ の $ l $ 文字目から $ r $ 文字目までに $ i $ 番目の アルファベットが何回出現するかを出力せよ。

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

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

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 $ は整数である。 ### Sample Explanation 1 $ f( $`abaaba`$ )= $`abaababaab` なので、$ f^{10^{100}}(S) $ の最初の $ 10 $ 文字を取り出したものも やはり `abaababaab` となっています。よって、$ 6 $ 文字目から $ 10 $ 文字目は `abaab` です。 `abaab` には `a` が $ 3 $ 回、 `b` が $ 2 $ 回使われていて、 `c` から `z` までは $ 1 $ 回も出てこないので、 出力するべき値は $ 1 $ 番目が $ 3 $ で、 $ 2 $ 番目が $ 2 $ で、それ以外の $ 24 $ 個が $ 0 $ となります。