← 返回题目列表

Codeforces · 309/B

B. 上下文广告

中文机器翻译题面 查看原题

广告已成为我们日常生活的一部分。现在,在技术进步的时代,我们需要您的想法来让广告变得更好!

在这个问题中,我们将研究上下文广告的简化版本。你有一个文本,恰好由 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