题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap CzatBBB

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

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

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

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

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

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

输入格式

第一行有四个整数 $n, k, a, b\ (2 \leq n \leq 10^{6}, 1 \leq k<n, n<a<b<10^{18}, b+1-a \leq 10^{6})$。输入的第二行有一个 $n$ 个字母组成的字符串，由英文字母表中的小写字母组成，表示字符串 $S$。

输出格式

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

11 3 12 13
abaaabababa

ba

样例 2

见附加文件下 [cza1ocen.in](file:cza1ocen.in) 和 [cza1ocen.out](file:cza1ocen.out)。

该样例满足 $n=20, k=3, a=30, b=40, S=\texttt{abcdabcd} \ldots$。

样例 3

见附加文件下 [cza2ocen.in](file:cza2ocen.in) 和 [cza2ocen.out](file:cza2ocen.out)。

该样例满足 $n=10^6, k=5, a=1000001, b=1000101, S=\texttt{zzzzz}\ldots\texttt{zzy}$。

样例 4

见附加文件下 [cza3ocen.in](file:cza3ocen.in) 和 [cza3ocen.out](file: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$