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 more or less as an inside joke within hacker culture, but has been around long enough that its use has become rather widespread.

Assignment

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 rules 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 may 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 |
                ||     ||