ReWord-wrap

Time limit1sMemory limit1024 MB

Summary

Given lines of text and a width w, rewrap the words so no line exceeds w characters without splitting any word.

Level: Easy3 of 10
Topics: String, Greedy, Implementation
Solved: No attempts yet

Problem

When the window of a text editor is resized, the words in the text often need to be rearranged so that they fit the screen window without splitting any word. This is called word-wrapping. Given a block of text, word-wrap it to fit a specific size.

Input

The first line contains an integer n, the number of datasets. Each dataset consists of:

An integer w, the number of characters per line, where $10 \le w \le 50$ .
An integer m, the number of lines of text to word wrap, where $1 \le m \le 100$ .
The m lines of text to word wrap.

Output

Output the text word wrapped to the proper number of characters, and print one blank line after each dataset.

Examples1

Example 1

Input

2
40
4
Chinua Achebe was born on November 16, 1930 into the Igbo
African ethnic group in southern Nigeria. He was raised in a
Christian family, but he was always fascinated by the
traditional African religion and culture.
35
4
Achebe uses the short story of a hard working man
in a war torn area with a bright outlook on life to act
as a model for other Africans affected by
the Nigerian Civil War.

Expected output

Chinua Achebe was born on November 16,
1930 into the Igbo African ethnic group
in southern Nigeria. He was raised in a
Christian family, but he was always
fascinated by the traditional African
religion and culture.

Achebe uses the short story of a
hard working man in a war torn area
with a bright outlook on life to
act as a model for other Africans
affected by the Nigerian Civil War.