题目背景

译自 XXXI Olimpiada Informatyczna - I etap CzatBBB。

题目描述

给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。

假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。

添加的规则如下所示： 对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母。如果 $R$ 在字符串 $S$ 中的其他地方都没有出现，则取 $X = a$。最后，我们扩展字符串 $S$，在其末尾添加字母 $X$。

例如，设 $S = \text{abaaabababa}$，$k = 3$ 则 $R$ 与后一个字母一起出现的字串为的：$\text{abaa}$、$\text{abab}$、$\text{abab}$。它最常与字母 $\text{b}$ 一起出现，因此我们在 $S$ 中加上 $\text{b}$，生成 $S' = \text{abaaabababab}$。

现在 $S' = \text{abaaabababab}$，$R = \text{bab}$，$R$ 与后一个字母一起出现的字串为：$\text{baba}$、$\text{baba}$，如 $\text{baba}$、$\text{baba}$，因此我们在 $S'$ 后面加上 $a$。

以此类推，这样的操作会进行无数次。

你的任务是编写一个程序，输出新字符串最后 $a$ 至 $b$ 个字符。

输入格式

第一行输入包含四个整数 $n$、$k$、$a$ 和 $b$。

第二行输入包含一个 $n$ 个字母的字符串，由小写英文字母组成的 $n$ 个字母字符串，表示单词 $S$。

输出格式

输出字符串 $S'$ 的第 $a$ 个字符 至第 $b$ 个字符，表示扩展单词 $S'$ 中位于以下位置的字母。

11 3 12 13
abaaabababa

ba

20 3 30 40
abcdabcdabcdabcdabcd

bcdabcdabcd

见附件

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

见附件

见附件

提示

对于所有的数据，$2\leq n\leq10^6$，$1\leq k<n<a<b<10^{18}$，$b+1-a\leq10^6$，串只含小写字母。