Time limit: 1 second
Memory limit: 256 MB
Amin contains a text
n
has n words and wants to sort them for this an integer
w
w chooses and wants it in the lines that have the maximum capacity
w
w characters, write.

To write these words, we write them down in the given order. We start from the first word and write it at the beginning of the first line. From then on, for each word, if we could write it in the same line by keeping a space (a space character or ' ') from the previous word (according to the capacity of that line), we do so, and otherwise, the word in The beginning of the next line will be written and this process continues.

We want to fix the problems that exist in small or large letters. It means that all written letters must be lowercase except for the first letter of the first word of the sentence. We know that sentences end with words that , ? Or! have

Now we want to justify all these lines! It means to put approximately equal number of spaces between the words of each line so that the last word of each line reaches the end of that line.

If a word is in one line, write it at the beginning of the line and fill the rest of the line with the space character.

Assume otherwise
m
to have m words in a line. We want in between
m
-
1
m−1 distance created by this
m
m word, put a number of space characters so that the difference in the number of spaces in these intervals is at most equal to one, and the last word has reached the end of the line.

In other words, for each numerical row, such as
k
There are k spaces between the words of that line
k
k or
k
+
1
be k+1.

Suppose you have to do this
r
r of distances
k
+
1
k+1 spaces, and
m
-
1
-
r
m−1−r to
k
We want k to have spaces
⌊
r
2
⌋
⌊
2
r
​
 ⌋ up from intervals
k
+
1
be k+1 between the first words of the line and
⌈
r
2
⌉
⌈
2
r
​
 ⌉ up to intervals
k
+
1
be k+1 between the last words of the line.

Finally, the number of characters printed per line must be exact
w
be w including spaces

entrance
At the entrance to you
t
t is given as an example.

1
≤
t
≤
100
1≤t≤100

In each example, in the first line of the number
n
n and number
w
w is given and in the second line
n
n words are separated by spaces.
1
≤
n
≤
100
1≤n≤100
2
≤
w
≤
2

000
2≤w≤2 000

Each string word is a maximum of 20 characters consisting of English uppercase and lowercase letters, at the end of some words at most one of the characters. or Or! Or, it is stuck.

Guaranteed to be the last word with one of the characters . or Or! ends

Quantity is guaranteed
w
w shall not be less than the length of the largest word given in each example.

output
Print the output requested in the problem as per the examples. To show the beginning and end of lines from the character | Use according to examples.

Example
Sample entry 1
2
2 6
caReEr dAyS!
6 10
Are you ready for this question?
Plain text
Sample output 1
|Career|
days! |
|Are you|
ready for
|this |
question? |
Plain text
Sample input 2
1
34 20
this is going to be a big sample to show how you should solve this problem. I hope this sample can show you what you want. Please, try to solve this problem. I love you!
Plain text
Sample output 2
This is going to be
|a big sample to show|
|how you should solve|
this problem. I hope
|this sample can show|
|you what you want.|
|Please, try to solve|
this problem. Love|
you! |                                                       write code in java