• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

امین یک متن حاوی $n$ کلمه دارد و می‌خواهد آن‌ها را مرتب کند برای این کار یک عدد صحیح $w$ انتخاب کرده و می‌خواهد آن را در سطر‌هایی که ظرفیت حداکثر $w$ کاراکتر دارند، بنویسد.

برای نوشتن این کلمات به ترتیب داده شده آن‌ها را یادداشت می‌کنیم. از کلمه اول شروع کرده و آن را در ابتدای سطر اول می‌نویسیم. از آن به بعد برای هر کلمه اگر تونستیم آن را با حفظ یک فاصله (یک کاراکتر space یا ' ') از کلمه قبل در همان سطر بنویسیم (با توجه به ظرفیت آن سطر) این کار را انجام می‌دهیم و در غیر این صورت کلمه در ابتدای سطر بعدی نوشته خواهد شد و این روند ادامه پیدا می‌کند.

می‌خواهیم اشکالاتی که در کوچک یا بزرگ بودن حروف وجود دارد را برطرف کنیم. یعنی همه حروف نوشته شده باید کوچک باشند به جز حرف اولِ کلمه‌ی اول جملات. می‌دانیم که جملات با کلماتی ختم می‌شوند که در انتهای آن‌ها . ، ؟ یا ! داشته باشند.

حال می‌خواهیم همه این سطرها را جاستیفای کنیم! یعنی تعداد تقریباً مساوی فاصله بین کلمات هر سطر قرار دهیم تا کلمه‌ی آخر هر سطر به انتهای آن سطر برسد.

اگر یک کلمه در یک سطر باشد آن را در ابتدای سطر می‌نویسیم و بقیه سطر را با کاراکتر space پرکنیم.

در غیر این صورت فرض کنید $m$ کلمه در یک سطر داشته باشیم. می‌خواهیم در بین $m-1$ فاصله ایجاد شده توسط این$m$ کلمه تعدادی کاراکتر space قرار دهیم به طوری که اختلاف تعداد spaceهای موجود در این فواصل حداکثر برابر یک باشد، همچنین کلمه آخر به انتهای سطر رسیده باشد.

به عبارت دیگر برای هر سطر عددی مانند $k$ وجود دارد که فاصله بین کلمات آن سطر همگی $k$ یا $k + 1$ باشد.

فرض کنید برای اینکار باید $r$ از فاصله‌ها $k + 1$ اسپیس، و $m-1-r$ تا $k$ تا اسپیس داشته باشند، می‌خواهیم $\lfloor \frac{r}{2}\rfloor$ تا از فواصل $k + 1$تایی بین کلمات ابتدایی سطر باشد و $\lceil \frac{r}{2} \rceil$ تا از فواصل $k + 1$تایی بین کلمات انتهایی سطر باشد.

در نهایت تعداد کاراکترهای چاپ شده در هر سطر باید دقیقاً $w$ باشد. با احتساب فاصله‌ها (یا همان spaceها)

ورودی

در ورودی به شما $t$ مثال داده می‌شود.

$$1 \le t \le 100$$

در هر مثال در سطر اول عدد $n$ و عدد $w$ داده می‌شود و در سطر دوم $n$ کلمه با فاصله از هم داده می‌شود.$$1 \le n \le 100$$ $$2 \le w \le 2\ 000$$

هر کلمه رشته حداکثر ۲۰ کاراکتری است که از حروف کوچک و بزرگ انگلیسی تشکیل شده است، به انتهای برخی از کلمات حداکثر یکی از کاراکترهای . یا ؟ یا ! یا, چسبیده است.

تضمین می‌شود آخرین کلمه با یکی از کاراکترهای . یا ؟ یا ! ختم می‌شود.

تضمین می‌شود مقدار $w$ از طول بزرگ‌ترین کلمه داده شده در هر مثال کمتر نخواهد بود.

خروجی

خروجی خواسته شده در مسئله را مطابق مثال‌ها چاپ کنید. برای نشان دادن ابتدا و انتهای خطوط از کارکتر | مطابق با مثال‌ها استفاده کنید.

مثال

ورودی نمونه ۱

2
2 6
caReEr dAyS!
6 10
Are You Ready For This Question?

خروجی نمونه ۱

|Career|
|days! |
|Are    you|
|ready  for|
|this      |
|question? |

ورودی نمونه ۲

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. love you!

خروجی نمونه ۲

|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!                |