Newspaper Text Justification

Place the words of each paragraph into a text box in order, without splitting words or crossing paragraphs; each line's content is width wide. A line that is not the last line of a paragraph and has multiple words must be fully justified: spaces are distributed evenly, with the remainder going to the leftmost gaps first. The last line of a paragraph and any line holding a single word must be centered, and when the leftover space is odd, the extra space goes on the right. Add one space and an asterisk on each outer side, with asterisk borders on top and bottom. Neither greedy breaking nor a minimum number of lines is required; any line breaking that satisfies the rules is accepted. No blank lines are inserted between paragraphs. The original site's examples omitted the alignment spaces in display; this site has filled them in.

This site's standard input and output are explicit.

输入格式

The first line contains width P; then P lines follow, each giving the word count and then the words of that paragraph. 5≤width≤50, 1≤P≤20, each paragraph has 1..10 words, and each word has length 1..width. On this site, words consist of printable non-whitespace ASCII characters (* is also allowed).

输出格式

Output the complete plain-text star frame, without a line count; every line has width+4 columns. Any line breaking that satisfies the layout rules is allowed and does not need to match the examples.

样例 1

输入：

16 3
2 Hello world
3 How areYou doing
7 Please look and align to the center

输出：

********************
*      Hello       *
*      world       *
*       How        *
*      areYou      *
*      doing       *
*      Please      *
*       look       *
*       and        *
*      align       *
*        to        *
*       the        *
*      center      *
********************

样例 2

输入：

5 1
3 a b c

输出：

*********
*   a   *
*   b   *
*   c   *
*********

样例 3

输入：

6 1
1 abc

输出：

**********
*  abc   *
**********

样例说明

Example 1: shows a valid layout with each word centered on its own line, for 12 content lines in total; Hello has length 5, so within the 16-column content area it gets 5 spaces on the left and 6 on the right, and each line is 20 columns including the outer margins and star frame. It can also be split greedily, as in the reference program, into 5 content lines; both are accepted. Example 2: the example puts a, b and c each on its own line with 2 spaces of padding on each side of the content area; the whole paragraph a b c on one line is equally valid. Example 3: abc has content width 3, leaving 3 spaces, 1 on the left and 2 on the right; with the outer margins and asterisks on both sides, the total width is 10.