Book Borders

A book is typeset with a fixed width font and a simple greedy algorithm that fills one line at a time. The contents of the book are a sequence of words, and each word has one or more characters.

Before typesetting you choose a maximum line length and call it $m$. A line holds at most $m$ characters, counting the spaces between words. The algorithm walks through the words in order and prints exactly one space between two consecutive words on the same line. If adding the current word to the current line would push it past $m$ characters, the algorithm starts a new line with that word instead.

|its.a.long...|          |its.a.long.way|
|way.to.the...|          |to.the.top.if.|
|top.if.you...|          |you.wanna.rock|
|wanna.rock.n.|          |n.roll........|
|roll.........|

The figure shows the text "its a long way to the top if you wanna rock n roll" typeset with maximum line lengths 13 and 14. The dots stand for space characters.

Fix one value of $m$. Take the first word of every line from top to bottom and join those words with a single space. The result is called the leading sentence. With maximum line length 14 the leading sentence in the figure is "its to you n".

You are given a text and two integers $a$ and $b$. For every maximum line length between $a$ and $b$ inclusive, find the length of the leading sentence. The length of a sentence is the number of characters it contains, counting its spaces.

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

The second line contains two integers $a$ and $b$, the ends of the interval described above.

Let $w$ be the length of the longest word in the text and let $z$ be the total number of characters in the text, counting the spaces. Then $1 \le w \le a \le b \le z \le 500000$.

Print $b - a + 1$ lines. The $k$-th line contains one integer, the length of the leading sentence when the maximum line length is $a - 1 + k$.