텍스트 정렬

이메일을 쓰는 일은 즐겁지만, 안타깝게도 각 줄의 길이가 제각각이라 보기에 그리 깔끔하지 않습니다. 이 문제에서 여러분이 할 일은, 한 문단을 (공백을 끼워 넣는 방식으로) 다시 배치하여 정렬 후 모든 줄의 길이가 같아지도록 만드는 서식 정렬 프로그램을 작성하는 것입니다. 문단의 마지막 줄도 예외 없이 같은 길이가 되어야 합니다.

가장 단순한 방법은 너무 짧은 줄의 단어 사이에 공백을 더 넣는 것입니다. 하지만 이것이 늘 가장 좋은 방법은 아닙니다. 다음 예를 살펴봅시다.

****************************
This is the example you are
actually considering.

모든 줄을 별표가 늘어선 길이만큼 맞추고 싶다고 합시다. 단순히 공백만 끼워 넣으면 다음과 같이 됩니다.

****************************
This is the example you  are
actually        considering.

그러나 둘째 줄의 큰 빈틈 때문에 다소 어색해 보입니다. 단어 "are"를 첫째 줄에서 둘째 줄로 옮기면 더 나은 결과를 얻습니다.

****************************
This  is  the  example   you
are  actually   considering.

이를 형식화하기 위해, 두 단어 사이의 각 빈틈(gap)에 나쁨 정도(badness) 를 부여합니다. 공백 $n$개로 이루어진 빈틈의 나쁨 정도는 $(n-1)^2$입니다. 프로그램의 목표는 모든 빈틈의 나쁨 정도의 합을 최소로 만드는 것입니다. 예를 들어 첫 번째 배치의 나쁨 정도는 $1 + 7^2 = 50$이고, 두 번째 배치의 나쁨 정도는 $1 + 1 + 1 + 4 + 1 + 4 = 12$로 훨씬 작습니다.

출력에서 모든 줄은 단어로 시작하고 단어로 끝나야 합니다. 즉, 줄의 맨 앞이나 맨 뒤에 빈틈이 있어서는 안 됩니다. 단 하나의 예외는 다음과 같습니다.

• 한 줄에 단어가 하나뿐이면 그 단어를 줄의 맨 앞에 두고, 그 줄이 정해진 너비보다 짧다면 그 줄에 $500$의 나쁨 정도를 부여합니다. (이 경우 줄의 길이는 그 단어의 길이와 같습니다.)

입력은 여러 개의 문단으로 이루어집니다. 각 문단 앞에는 그 문단의 목표 너비를 나타내는 정수 $n$ 하나가 한 줄에 주어집니다 ($1 \le n \le 80$).

각 문단은 한 줄 이상으로 이루어지며, 각 줄에는 한 개 이상의 단어가 들어 있습니다. 단어는 ASCII 코드 33부터 126까지의 문자로 이루어지고, 하나 이상의 공백으로 구분됩니다. 어떤 단어도 그 문단의 목표 너비보다 길지 않습니다. 한 문단에 들어 있는 모든 단어의 길이 합은 10000자를 넘지 않습니다.

각 문단은 정확히 한 개의 빈 줄로 끝납니다. 문단의 개수에는 제한이 없습니다.

입력은 너비가 $n = 0$인 문단 설명으로 끝나며, 이 문단은 처리하지 않습니다.

각 문단에 대해, 위에서 설명한 방식으로 정렬한 같은 텍스트를 출력합니다 (문단마다 독립적으로 처리합니다). 정렬된 문단의 모든 줄은 같은 너비 $n$을 가집니다. 다만 단어가 하나뿐인 줄은 더 짧을 수 있습니다.

한 문단을 최소 나쁨 정도가 같은 여러 가지 방법으로 정렬할 수 있다면, 다음 규칙으로 출력할 배치를 고릅니다. 두 배치 $A$와 $B$가 있을 때, 읽는 순서대로 단어 사이 빈틈들을 살펴 길이가 처음으로 달라지는 빈틈을 찾습니다. 그 빈틈이 더 큰 배치는 출력하지 않습니다. (즉, 최소 나쁨 정도를 가지는 모든 배치 중에서 빈틈 길이의 수열이 사전순으로 가장 작은 것을 출력합니다.)

서로 이웃한 두 문단 사이에는 빈 줄을 하나 출력합니다.