Setting a Newspaper Column

A newspaper prints articles in narrow columns where both edges are straight. Given the article text and the column width, return the column as a list of lines. Every line must be exactly width characters long.

1. Words. The words of text are the pieces separated by spaces (there may be several spaces in a row, or spaces at the ends). A word longer than width is first cut into pieces of width characters, left to right (the last piece may be shorter); each piece then counts as a word of its own.
2. Filling. Fill lines from left to right. A word goes on the current line if it fits with a single space before it; otherwise it starts a new line.
3. Stretching. On every line except the last, widen the gaps between words until the line is width long. All gaps get the same number of spaces, except that when the spaces do not divide evenly the gaps on the left get one extra space each.
4. Special lines. A line holding only one word, and the last line, keep single spaces between words and are padded with spaces on the right up to width.

If text has no words, return [].

Examples

Input:  text = "the quick brown fox jumps over the lazy dog", width = 16
Output: ["the  quick brown",
         "fox  jumps  over",
         "the lazy dog    "]

Input:  text = "a  bb   extraordinary", width = 6
Output: ["a   bb",
         "extrao",
         "rdinar",
         "y     "]

Constraints

• 1 <= width <= 80
• 0 <= len(text) <= 5000; text contains lowercase letters, punctuation and spaces only

Goals

• Pack words greedily into lines of a fixed width
• Share extra spaces between the gaps with a precise left-first rule
• Handle one-word lines, the last line and words too long for a line