You are given an array of strings words and an integer maxWidth. Format the text so that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach, that is, pack as many words as possible in each line. Add extra spaces (' ') when necessary so that each line contains exactly maxWidth characters.

The extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words. Remaining spaces should be added at the end of the line.

A word is defined as a character sequence consisting of non-space characters only.

---

Example 1

Input

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

Output

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

---

Example 2

Input

words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16

Output

[
"What   must   be",
"acknowledgment ",
"shall be        "
]

Explanation

• The second line contains only one word, so no extra spaces are inserted between words.
• The last line is always left-justified, so the words have a single space between them and the remaining spaces are added after the last word.

---

Example 3

Input

words = [
"Science","is","what","we","understand",
"well","enough","to","explain","to",
"a","computer.","Art","is","everything",
"else","we","do"
]
maxWidth = 20

Output

[
"Science  is  what we",
"understand      well",
"enough to explain to",
"a  computer.  Art is",
"everything  else we",
"do                  "
]

Explanation

Words are greedily placed into each line. The spaces between words are distributed from left to right whenever they cannot be divided equally. The final line is left-justified with trailing spaces.

---

Input Format

• Line 1: Integer N — the number of words.
• The next N lines each contain a string representing one word.
• The last line contains an integer maxWidth — the required width of each formatted line.

---

Output Format

Return an array of formatted line strings.

Each line must contain exactly maxWidth characters.

---

Constraints

• 1 ≤ words.length ≤ 10^5
• 1 ≤ words[i].length ≤ 100
• 1 ≤ maxWidth ≤ 100
• Each word consists of printable non-space characters.

---

Sample Case 0

Sample Input 0

7
This
is
an
example
of
text
justification.
16

Sample Output 0

This    is    an
example  of text
justification.

Explanation

The words are packed greedily. Extra spaces are added between words to make every line exactly 16 characters long.

---

Function Signature

vector<string> formatText(vector<string> words, int max_width)

Return

Return a vector<string> containing the fully justified text, where every line has exactly maxWidth characters.