F - SS Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1100 点

問題文

同じ文字列を 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 で写した文字列のことを指します。

制約

  • 2 \leq |S| \leq 2\times 10^5
  • 1 \leq l \leq r \leq 10^{18}
  • S は小文字のアルファベットのみからなる偶文字列である。
  • l,r は整数である。

入力

入力は以下の形式で標準入力から与えられる。

S
l r

出力

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

入力例 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) の最初の 10 文字を取り出したものも やはり abaababaab となっています。よって、6 文字目から 10 文字目は abaab です。 abaab には a が 3 回、 b が 2 回使われていて、 c から z までは 1 回も出てこないので、 出力するべき値は 1 番目が 3 で、 2 番目が 2 で、それ以外の 24 個が 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

Score : 1100 points

Problem Statement

We will call a string that can be obtained by concatenating two equal strings an even string. For example, xyzxyz and aaaaaa are even, while ababab and xyzxy are not.

For a non-empty string S, we will define f(S) as the shortest even string that can be obtained by appending one or more characters to the end of S. For example, f(abaaba)=abaababaab. It can be shown that f(S) is uniquely determined for a non-empty string S.

You are given an even string S consisting of lowercase English letters. For each letter in the lowercase English alphabet, find the number of its occurrences from the l-th character through the r-th character of f^{10^{100}} (S).

Here, f^{10^{100}} (S) is the string f(f(f( ... f(S) ... ))) obtained by applying f to S 10^{100} times.

Constraints

  • 2 \leq |S| \leq 2\times 10^5
  • 1 \leq l \leq r \leq 10^{18}
  • S is an even string consisting of lowercase English letters.
  • l and r are integers.

Input

Input is given from Standard Input in the following format:

S
l r

Output

Print 26 integers in a line with spaces in between. The i-th integer should be the number of the occurrences of the i-th letter in the lowercase English alphabet from the l-th character through the r-th character of f^{10^{100}} (S).

Sample Input 1

abaaba
6 10

Sample Output 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

Since f(abaaba)=abaababaab, the first ten characters in f^{10^{100}}(S) is also abaababaab. Thus, the sixth through the tenth characters are abaab. In this string, a appears three times, b appears twice and no other letters appear, and thus the output should be 3 and 2 followed by twenty-four 0s.

Sample Input 2

xx
1 1000000000000000000

Sample Output 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

Sample Input 3

vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000

Sample Output 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