{"raw_statement":[{"iden":"background","content":"译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [CzatBBB](https://sio2.mimuw.edu.pl/c/oi31-1/p/cza/)。\n"},{"iden":"statement","content":"给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。\n\n假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。\n\n添加的规则如下所示： 对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母，如果有多个出现频率最高的字母，取最小的一个。如果 $R$ 在字符串 $S$ 中的其他地方都没有出现，则取 $X = a$。最后，我们扩展字符串 $S$，在其末尾添加字母 $X$。\n\n例如，设 $S = \\text{abaaabababa}$，$k = 3$ 则 $R$ 与后一个字母一起出现的字串为的：$\\text{abaa}$、$\\text{abab}$、$\\text{abab}$。它最常与字母 $\\text{b}$ 一起出现，因此我们在 $S$ 中加上 $\\text{b}$，生成 $S' = \\text{abaaabababab}$。\n\n现在 $S' = \\text{abaaabababab}$，$R = \\text{bab}$，$R$ 与后一个字母一起出现的字串为：$\\text{baba}$、$\\text{baba}$，如 $\\text{baba}$、$\\text{baba}$，因此我们在 $S'$ 后面加上 $a$。\n\n以此类推，这样的操作会进行无数次。\n\n你的任务是编写一个程序，输出新字符串最后 $a$ 至 $b$ 个字符。"},{"iden":"input","content":"第一行输入包含四个整数 $n$、$k$、$a$ 和 $b$。\n\n第二行输入包含一个 $n$ 个字母的字符串，由小写英文字母组成的 $n$ 个字母字符串，表示单词 $S$。"},{"iden":"output","content":"输出字符串 $S'$ 的第 $a$ 个字符 至第 $b$ 个字符，表示扩展单词 $S'$ 中位于以下位置的字母。"},{"iden":"note","content":"对于所有的数据，$2\\leq n\\leq10^6$，$1\\leq k<n<a<b<10^{18}$，$b+1-a\\leq10^6$，串只含小写字母。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $n\\leq100$，$b\\leq1000$ | 8 |\n| 2 | $b\\leq 10^8$ | 10 |\n| 3 | $n\\leq 500$，后缀 $R$ 的前一次出现将始终存在，并且每次出现后都会有相同的字母  | 16 |\n| 4 | 后缀 $R$ 的前一次出现将始终存在，并且每次出现后都会有相同的字母 | 10 |\n| 5 | $k\\leq20$，$b\\leq 10^{10}$，串只含 `ab` | 16 |\n| 6 | 无任何限制  | 40 |"}],"translated_statement":null,"sample_group":[["11 3 12 13\nabaaabababa\n","ba\n"],["20 3 30 40\nabcdabcdabcdabcdabcd\n","bcdabcdabcd\n"],["见附件","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n"],["见附件","见附件"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}