Your task is to format a given text fragment as a banner having a predefined width. The text fragment should be cleaned up, split across multiple lines, centered and framed within a rectangle of stars. The following example shows what the final result should look like.

Strictly follow these instructions to format the banner. 

1. Clean the given text by removing spaces at the front and the back and reducing consecutive spaces into a single space.

2. If the text is shorter than the predefined width, the banner should be made as wide as the text itself (see second example below).

3. If the text is longer than the predefined width, the text should be written out across multiple lines. Each line should contain the maximum number of remaining words that fits the predefined width. The words of the given text are separated by spaces. Punctuation marks and other special characters belong to the word to which they are attached.

4. The text fragment that fits a single line should be centered across the width of the banner. Use the string method center to center the text fragment.

5. Put extra stars and spaces around the text as illustrated in the above example. 

Your submitted solution should put every character at exactly the right position, so the evaluation will be quite strict.

Input

A line of text followed by a line containing the predefined width $$b \in \mathbb{N_0}$$ of the banner. You might assume that the longest word in the text fragment is not longer than the predefined width $$b$$.

Output

The text formatted as a banner having width $$b$$, according to procedure outlined in the introduction. 

Example

Input:

If evolution  really works,  how come mothers  only   have two hands? 
26

Output:

********************************
*                              *
*  If evolution really works,  *
*  how come mothers only have  *
*          two hands?          *
*                              *
********************************

Example

Input:

    And  now   for    something     completely      different.      
1000

Output:

*************************************************
*                                               *
*  And now for something completely different.  *
*                                               *
*************************************************