题目背景

A book is being typeset using a fixed width font and a simple greedy algorithm to fill each line. The book contents is just a sequence of words, where each word contains one or more characters.

题目描述

Before typesetting, we choose a maximum line length and denote this value with m. Each line can be at most m characters long including the space characters between the words. The typesetting algorithm simply processes words one by one and prints each word with exactly one space character between two consecutive words on the same line. If printing the word on the current line would exceed the maximum line length m, a new line is started instead.

You are given a text to be typeset and are experimenting with different values of the maximum line length m. For a fixed m, the leading sentence is a sentence (a sequence of words separated with a single space character) formed by the first words of lines top to bottom. In the example above, when the sample text is typeset with the maximum line length 14, the leading sentence is “its to you n”.

Given a text and two integers a and b, find the length of the leading sentence for every candidate maximum line length between a and b inclusive. The length of a sentence is the total number of characters it contains including the space characters.

输入格式

The first line contains the text to be typeset – a sequence of words separated by exactly one space character. Each word is a string consisting of one or more lowercase letters from the English alphabet.

The second line contains two integers a and b – the edges of the interval we are interested in, as described above.

It is guaranteed that $1<=w<=a<=b<=z<=500 000$, where w is the length of the longest word in the text and z is the total number of characters in the text including the space characters.

输出格式

Output $b - a + 1$ lines – the $k$-th of those lines should contain a single integer – the total length of the leading sentence when the maximum line length is equal to $a - 1 + k$.

题目大意

现有一本书,用固定宽度的字体和简单的贪婪算法来填充每行文字。书的内容是一个单词序列，每个单词包含一个或多个字符。

排版前，我们选择一个最大的行长度，并用m表示这个值。每行最多可以有m个字符，包括单词之间的空格字符。请使用排版算法简单地逐个处理单词，并在同一行上的两个连续单词之间打印每个单词，每个单词只有一个空格字符。而且如果在当前行上打印该字超过最大行长度m，则开始新行。 现在你得到了一个要排版的文本，并且正在试验最大行长度m的不同值。对于固定m，前导句是一个句子(由一个空格字符分隔的一系列单词)，由行的第一个单词从上到下组成。在上例中，当样本文本以最大行长度14进行排版时，前导句是“对你来说是n”（its to you n） 给定一个文本和两个整数a和b，找出a和b之间每个候选最大行长度的前导句长度。句子的长度是它包含的字符总数，包括空格字符

输入格式： 第一行包含要排版的文本——由一个空格字符分隔的一系列单词。每个单词都是一个字符串，由英语字母表中的一个或多个小写字母组成。 第二行包含两个整数a和b——如上所述的区间边缘。保证1<=w <=a<=b<=z<=50000, 其中w是文本中最长单词的长度，z是文本中包括空格字符的字符总数。

输出格式 输出b-a+1行——这些行的第k行应该包含一个整数——最大行长度等于a-1+k时前导句的总长度。

输入输出样例

输入样例#1

its a long way to the top if you wanna rock n roll
13 16

输出样例#1

22
12
12
15

its a long way to the top if you wanna rock n roll
13 16

22
12
12
15

提示

Central Europe Regional Contest 2015 Problem B