The computer program cowsay generates ASCII pictures of a cow with a message.

+----------------------------+
| Moo may represent an idea, |
|  but only the cow knows.   |
+----------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

The program initially started of as a kind of inside joke within hacker culture, but has been around long enough that its use has become rather widespread. Your task is to write a program that can be used to generate ASCII pictures of a cow with a message that is displayed with a certain width. The text fragment should be cleaned up, split across multiple lines, centered and framed within a speech bubble.

Strictly follow these instructions to format the speech bubble. 

1. Clean the given text by removing leading and trailing spaces and reducing consecutive spaces into a single space.
2. If the text is shorter than the maximal allowed width, the speech bubble should be made as wide as the text itself (see second example below).
3. If the text is longer than the maximal allowed width, the text should be split across multiple lines. Each line should contain the maximum number of remaining words that fits the maximal allowed 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 speech bubble (according to the rulses that are implemented by the string method center).
5. Put additional dashes, plus symbols, vertical bars and spaces around the text as illustrated in the examples.

Your submitted solution will be compared character by character to the correct solution, so it is crucial to put all characters at exactly the right position.

Input

A line of text followed by a line containing the maximal allowed width $w \in \mathbb{N_0}$ of the speech bubble. You might assume that the longest word in the text fragment is not longer than the maximal allowed width $w$.

Output

The given text formatted in a speech bubble having width $w$, according to procedure outlined in the introduction. A fixed ASCII image of the cow should immediately follow the speech bubble.

Example

Input:

Moo   may   represent   an  idea,  but only the cow knows.
26

Output:

+----------------------------+
| Moo may represent an idea, |
|  but only the cow knows.   |
+----------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Example

Input:

Moo   may   represent   an  idea,  but only the cow knows.
1000

Output:

+----------------------------------------------------+
| Moo may represent an idea, but only the cow knows. |
+----------------------------------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Example

Input:

Moo   may   represent   an  idea,  but only the cow knows.
9

Output:

+-----------+
|  Moo may  |
| represent |
|  an idea, |
|  but only |
|  the cow  |
|   knows.  |
+-----------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Het computerprogramma cowsay genereert ASCII-afbeeldingen van een koe met een bijhorend bericht.

+----------------------------+
| Moo may represent an idea, |
|  but only the cow knows.   |
+----------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Het programma was oorspronkelijk bedoeld als een soort inside joke binnen de wereld van de hackers, maar bestaat ondertussen al zo lang dat het gebruik ervan wijd verspreid geraakt is. Je opdracht bestaat erin een gegeven boodschap uit te schrijven als een koe die de boodschap uitspreekt. Hierbij moet de tekst van de boodschap opgeschoond worden, en uitgeschreven worden in een tekstballon met een gegeven maximale breedte. Daarbij moet de tekst eventueel in verschillende regels opgebroken worden, die gecentreerd in de tekstballen weergegeven worden.

Volg strikt de volgende procedure op om de tekstballon op te maken.

1. Schoon de tekst van de gegeven boodschap op door spaties vooraan en achteraan te verwijderen, en meerdere spaties na elkaar te reduceren tot één enkele spatie.
2. Als de tekst niet langer is dan de gegeven breedte, dan moet de tekstballon niet breder gemaakt worden dan de lengte van de tekst (zie tweede voorbeeld hieronder).
3. Als de tekst wel langer is dan de gegeven breedte, dan moet de tekst uitgeschreven worden over verschillende regels, waarbij telkens het maximum aantal resterende woorden moet uitgeschreven worden dat de gegeven breedte niet overschrijdt. De woorden van de tekst worden hierbij van elkaar gescheiden door spaties. De leestekens behoren dus tot het woord waar ze aan vasthangen.
4. Het tekstfragment dat op één regel past moet gecentreerd uitgeschreven worden (volgens de regels voor centreren die geimplementeerd worden door de stringmethode center).
5. Plaats extra koppeltekens, plustekens, verticale strepen en spaties rondom de tekst zoals aangegeven in de voorbeelden.

Bij de controle van je oplossing zullen we er strikt op toezien dat alle karakters op de juiste plaats gezet worden in de uitvoer.

Invoer

Een regel met de tekst van een gegeven boodschap, gevolgd door een regel met een gegeven breedte $b \in \mathbb{N_0}$. Je mag ervan uitgaan dat het langste woord in de tekst niet langer is dan de gegeven breedte $b$.

Uitvoer

De tekst van de gegeven boodschap opgemaakt als een tekstballon, gevolgd door de vaste ASCII-afbeelding van een koe. De tekst in de tekstballon heeft een maximale breedte $b$, volgens de procedure die in de inleiding werd beschreven.

Voorbeeld

Invoer:

Moo   may   represent   an  idea,  but only the cow knows.
26

Uitvoer:

+----------------------------+
| Moo may represent an idea, |
|  but only the cow knows.   |
+----------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Voorbeeld

Invoer:

Moo   may   represent   an  idea,  but only the cow knows.
1000

Uitvoer:

+----------------------------------------------------+
| Moo may represent an idea, but only the cow knows. |
+----------------------------------------------------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

Voorbeeld

Invoer:

Moo   may   represent   an  idea,  but only the cow knows.
9

Uitvoer:

+-----------+
|  Moo may  |
| represent |
|  an idea, |
|  but only |
|  the cow  |
|   knows.  |
+-----------+
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||