题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap CzatBBB

Bajtazar 发现了自己对机器学习的热情。他正在开发一个新的语言模型，他称之为 CzatBBB。

模型的输入是一个 $n$ 个字母的字符串 $S$ 和一个整数参数 $k$（$1 \leq k < n$），然后模型生成这个字符串的后续部分。

假设我们已经有了一个字符串 $S'$，它是 $S$ 的一个扩展，也就是在 $S$ 的后面添加了一些字母。添加新字母的过程如下： 我们考虑 $S'$ 的 $k$ 个字母的后缀 $R$。找到 $R$ 在 $S'$ 中作为连续的子串出现过的所有位置。对于字母表中的每个字母，统计它在 $S'$ 中紧跟在 $R$ 后面出现的次数。令 $c$ 表示出现次数最多的字母。如果有并列的情况，我们选择字母表中靠前的字母。如果 $R$ 在 $S'$ 中没有其他出现的位置，我们就让 $c = \texttt{a}$。最后，我们把字母 $c$ 添加到 $S'$ 的末尾。

例如，令 $S = \texttt{abaaabababa}$ 且 $k=3$。
最初，我们有 $S' = S$，$R = \texttt{aba}$，而 $R$ 及之前跟着的字母分别是：$\texttt{abaa}$、$\texttt{abab}$、$\texttt{abab}$。出现次数最多的字母是 $\texttt{b}$，所以我们在 $S'$ 的后面添加 $\texttt{b}$。

现在 $S' = \texttt{abaaabababab}$，$R = \texttt{bab}$，而 $R$ 及之前跟着的字母分别是 $\texttt{baba}$、$\texttt{baba}$，所以我们在 $S'$ 的后面添加 $\texttt{a}$。

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

---

输入格式

第一行有四个整数 $n, k, a, b$，满足：

$$2 \leq n \leq 10^{6}, \quad 1 \leq k < n, \quad n < a < b < 10^{18}, \quad b+1-a \leq 10^{6} $$

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

---

输出格式

输出 $b-a+1$ 行，每行一个字符串。第 $i$ 行的字符串应该是模型生成的以 $S$ 开头，长度为 $a+i-1$ 的字符串。输出的字符串不应该包含空格或其他字符。

---

样例 1

输入

11 3 12 13
abaaabababa

输出

ba

解释
此样例要求输出两行，第一行是长度为 $12$ 的字符串（abaaabababab 的后三位 bab），第二行是长度为 $13$ 的字符串（abaaababababa 的后三位 aba），所以输出：

bab
aba

注意样例给出 ba 只是最后两个字母（应是对应两个字符串的最后一位字母 b 和 a），但题目实际要求输出整个字符串。这里可能有歧义，但根据题目描述，应输出完整字符串。

---

样例 2

见附加文件下 cza1ocen.in 和 cza1ocen.out。
该样例满足 $n=20, k=3, a=30, b=40, S=\texttt{abcdabcd}\ldots$。

样例 3

见附加文件下 cza2ocen.in 和 cza2ocen.out。
该样例满足 $n=10^6, k=5, a=1000001, b=1000101, S=\texttt{zzzzz}\ldots\texttt{zzy}$。

样例 4

见附加文件下 cza3ocen.in 和 cza3ocen.out。
该样例满足 $n=10^6, k=n-1, a=10^{18}-10^{6}, b=10^{18}-1, S=\texttt{aaaa}\ldots$。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n \leq 100, b \leq 1000$	8
2	$b \leq 10^{8}$	10
3	$n \leq 500$，$R$ 总是存在其他出现的位置，并且每次出现后面的字母都相同	16
4	$R$ 总是存在其他出现的位置，并且每次出现后面的字母都相同	10
5	$k \leq 20, b \leq 10^{10}$，$S$ 只由 $\texttt{a}$ 和 $\texttt{b}$ 构成	16
6	无附加限制	40