广告已成为我们日常生活的一部分。现在,在技术进步的时代,我们需要您的想法来让广告变得更好!
在这个问题中,我们将研究上下文广告的简化版本。你有一个文本,恰好由 n 个单词组成。标准的广告横幅正好有r行,每行最多可以包含c个字符。潜在客户总是喜欢看到大量广告,因此您应该确定横幅上可以写的文本中的最大连续单词数。横幅中一行中的单个单词应以空格分隔。您可以一次插入多个空格。请注意,不允许断词,即文本中的每个单词必须恰好占据横幅中的一行。此外,你不能改变词序,也就是说,如果你从上到下、从左到右连续阅读横幅文本,你应该得到广告文本的一些连续部分。
更正式地说,该语句可以这样写。假设所有单词都按照它们在广告文本中出现的顺序从 1 到 n 进行索引。然后你必须选择所有的单词,从第 i 个单词开始到第 j 个单词结束(1 ≤ i ≤ j ≤ n),这样所有的单词都可以写在横幅上。必须有尽可能多的单词。请参阅示例以获取说明。
输入
第一个输入行包含三个整数 n、r、c (1 ≤ n、r、c ≤ 106;r × c ≤ 106)。下一行包含一个由 n 个单词组成的文本。这些单词仅由小写英文字母组成,并且不为空。行中的单词由单个空格分隔。所有单词的字符总数不超过5·106。
输出
最多打印r行,每行最多打印c个字符——最优广告横幅。如果有多个广告横幅,则打印其中任何一个。
请注意,横幅的某些行可以为空。您可以不打印这些行。
示例
输入 #1
9 4 12 this is a sample text for croc final round
输出 #1
this is a sample text for croc final round
输入 #2
9 1 9 this is a sample text for croc final round
输出 #2
this is a
输入 #3
6 2 3 croc a a a croc a
输出 #3
a a a
输入#4
2 2 5 first second
输出#4
first