{"raw_statement":[{"iden":"problem statement","content":"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.\nFor 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$.\nYou 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)$.\nHere, $f^{10^{100}} (S)$ is the string $f(f(f( ... f(S) ... )))$ obtained by applying $f$ to $S$ $10^{100}$ times."},{"iden":"constraints","content":"*   $2 \\leq |S| \\leq 2\\times 10^5$\n*   $1 \\leq l \\leq r \\leq 10^{18}$\n*   $S$ is an even string consisting of lowercase English letters.\n*   $l$ and $r$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$\n$l$ $r$"},{"iden":"sample input 1","content":"abaaba\n6 10"},{"iden":"sample output 1","content":"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\n\nSince $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 $0$s."},{"iden":"sample input 2","content":"xx\n1 1000000000000000000"},{"iden":"sample output 2","content":"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"},{"iden":"sample input 3","content":"vgxgpuamkvgxgvgxgpuamkvgxg\n1 1000000000000000000"},{"iden":"sample output 3","content":"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"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}