{"problem":{"name":"SS","description":{"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. For a non-empty string ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc077_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n$l$ $r$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc077_d","tags":[],"sample_group":[["abaaba\n6 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\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."],["xx\n1 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\n1 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"]],"created_at":"2026-03-03 11:01:14"}}