Text Justification

You are given an array of words and a target line width maxWidth. Arrange the words into lines of justified text so that each line has exactly maxWidth characters, following these rules:

• Pack as many words as possible into each line without exceeding maxWidth, using at least one space between consecutive words.
• For every line except the last one, distribute the extra spaces as evenly as possible among the gaps between words on that line. If the extra spaces cannot be split evenly, the leftover space slots go to the leftmost gaps first, so earlier gaps get one more space than later gaps.
• A line that contains only a single word should have that word left-justified, with the remaining space padded on the right.
• The last line of the output should be left-justified: words are separated by a single space each, and any remaining width is padded with trailing spaces so the line still has length maxWidth.
• You may assume every individual word's length is strictly less than maxWidth, so no word ever needs to be split.

Return the resulting lines as a list of strings, each of length exactly maxWidth.

Examples

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16

Output: ["This is an","example of text","justification. "]

Explanation:

• Line 1 fits 'This is an' with 5 extra spaces spread across 2 gaps, giving 3 and 2.
• Line 2 fits 'example of text' with 2 extra spaces across 2 gaps, giving 2 and 1.
• The last line 'justification.' is left-justified with trailing spaces to reach width 16.

Example 2:

Input: words = ["Listen"], maxWidth = 10

Output: ["Listen "]

Explanation:

There is only one word and one line, so it is left-justified with the remaining 4 spaces padded on the right.

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= maxWidth
• words[i] consists of only lowercase and uppercase English letters.
• 1 <= maxWidth <= 100