Leading Sentence Typesetting

Given a text to be typeset and two integers a and b, the task is to determine the length of the leading sentence for every candidate maximum line length m where a ≤ m ≤ b. The typesetting algorithm works as follows:

Let \( m \) be the maximum line length (in characters). The text is split into words by spaces. Words are printed one by one on a line with exactly one space character between consecutive words. If printing the next word would exceed \( m \) characters, a new line is started. The leading sentence is defined as the sentence formed by taking the first word from each line (in order) and joining them with a single space. Its length is the sum of the lengths of these words plus the number of spaces between them (i.e. if there are \( k \) words then the length equals \( \sum_{i=1}^{k} \ell(w_i) + (k-1) \), where \( \ell(w_i) \) denotes the length of the i-th word).

inputFormat

The first line contains the text to be typeset. The text consists of one or more words separated by a single space.

The second line contains two integers a and b (with \(1 \leq a \leq b \leq 10^9\)), representing the range of candidate maximum line lengths.

outputFormat

Output exactly \( b - a + 1 \) lines. The i-th line (starting from 0) should contain a single integer: the length of the leading sentence when the text is typeset using m = a + i.

sample

the quick brown fox jumps over the lazy dog
10 12

23
23
19