Bajtazar 发现了自己对机器学习的热情。他目前正在开发一个名为 CzatBBB（Bajtazar 的 Bajtocki 机器人缩写）的新语言模型。

该模型接收一个长度为 $n$ 的字符串 $S$ 和一个参数 $k$（整数 $1 \le k < n$），然后生成该字符串的后续内容。

假设我们已经有了字符串 $S'$，它是 $S$ 的某种扩展。添加新字符的过程如下（另请参阅下文示例）：考虑 $S'$ 的长度为 $k$ 的后缀 $R$，并查看 $S'$ 中所有 $R$ 之前的出现位置（作为连续子串）。然后，对于字母表中的每个字母，统计它在 $S'$ 中紧跟在 $R$ 之后出现的次数。设 $c$ 为出现次数最多的字母。如果出现次数相同，则选择字母表中较靠前的字母；如果 $R$ 在 $S'$ 的其他任何地方都没有出现过，则令 $c = \text{'a'}$。最后，通过在末尾添加字母 $c$ 来扩展字符串 $S'$。

例如，设 $S = \text{abaaabababa}$ 且 $k = 3$。此时 $S' = S$，$R = \text{aba}$，且 $R$ 之前出现的后续字符为：$\text{abaa}, \text{abab}, \text{abab}$。出现次数最多的是字母 $\text{'b'}$，因此我们将 $\text{'b'}$ 添加到 $S'$ 中。

现在 $S' = \text{abaaabababab}$，$R = \text{bab}$，且 $R$ 之前出现的后续字符为：$\text{baba}, \text{baba}$，因此我们将 $\text{'a'}$ 添加到 $S'$ 中。

你的任务是编写一个程序，实现 Bajtazar 设计的模型。

输入格式

输入的第一行包含四个整数 $n, k, a$ 和 $b$ ($2 \le n \le 10^6, 1 \le k < n, n < a < b < 10^{18}, b + 1 - a \le 10^6$)。输入的第二行包含一个由小写英文字母（'a' – 'z'）组成的长度为 $n$ 的字符串，表示字符串 $S$。

输出格式

输出一个长度为 $b + 1 - a$ 的字符串，表示扩展后的字符串 $S'$ 从第 $a$ 位到第 $b$ 位（包含）的字符。换句话说，假设在初始字符串 $S$ 之后添加了 $b - n$ 个字符，我们想要输出这些添加字符中的最后 $b + 1 - a$ 个。

样例

输入格式 1

11 3 12 13
abaaabababa

输出格式 1

ba

子任务