Fully Justified Lines

You are given a list of strings words and an integer width. No word contains a space, and no word is longer than width.

Lay the words out, in order, on lines of exactly width characters each:

• Each line takes as many of the next words as fit with at least one space between adjacent words. The following line starts with the first word that did not fit.
• On every line except the last, if the line holds two or more words, its spaces are shared across the gaps between its words so that every gap is as close to equal as possible. If the spaces can't be shared evenly, the gaps on the left get one more space than the gaps on the right.
• The last line, and any line that holds only one word, is not spread out: its words are separated by single spaces and the rest of the line is filled with spaces on the right.

Return the lines as a list of strings.

Examples

Example 1

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], width = 16
Output: ["This    is    an", "example  of text", "justification.  "]
Explanation: "This", "is", and "an" have 8 letters and "example" would push the line past 16, so the 8 spare spaces are split across the 2 gaps as 4 and 4. "example", "of", and "text" have 13 letters, so 3 spaces go across 2 gaps as 2 and 1, the left gap getting the extra one. The last line holds one word and is padded with 2 spaces on the right.

Example 2

Input: words = ["What", "must", "be", "acknowledgment", "shall", "be"], width = 16
Output: ["What   must   be", "acknowledgment  ", "shall be        "]
Explanation: The first line has 10 letters and 6 spaces split evenly as 3 and 3. "acknowledgment" is alone on its line because "shall" doesn't fit next to it, so it is padded on the right rather than spread. The last line is "shall be" followed by 8 spaces, not "shall     be", because the last line is never spread out.

Example 3

Input: words = ["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"], width = 20
Output: ["Science  is  what we", "understand      well", "enough to explain to", "a  computer.  Art is", "everything  else  we", "do                  "]
Explanation: The first line has 15 letters and 5 spaces across 3 gaps, so the gaps are 2, 2, and 1. "understand" and "well" leave 6 spaces for a single gap. "enough to explain to" fills its 20 characters with single spaces. The last line is "do" followed by 18 spaces.