LJUST

Nili company는 간단한 텍스트 편집기를 개발하려고 한다. 개발팀의 일원인 Mohammad는 양쪽 정렬(justify) 기능을 맡았다. 워드 프로세서를 써 본 적이 있다면 이 기능을 알고 있을 것이다. Mohammad를 도와 여러 줄을 입력받아 양쪽 정렬하여 출력하는 프로그램을 작성하라.

프로그램을 작성할 때 다음을 지켜야 한다.

• 각 줄은 하나의 문단이다.
• 양쪽 정렬을 하려면 단어 사이에 공백을 추가하여 줄을 채운다. 공백은 왼쪽에서 오른쪽으로 단어 사이에 고르게 분배한다. 모든 공백을 첫 번째 단어 뒤에 몰아넣으면 안 된다.
• 줄의 문자 수가 floor(C/2) 이상일 때만 양쪽 정렬한다.
• C보다 긴 줄은 다음 줄로 넘긴다.
• 양쪽 정렬된 줄은 공백으로 시작하거나 끝나면 안 된다.
• 빈 줄은 삭제하지 않는다. 빈 줄이란 공백이 아닌 문자가 하나도 없는 줄이다.

첫째 줄에는 줄당 최대 문자 수 C가 주어진다 (C >= 50).

다음 N개 줄 (N < 100000)에는 각각 W개의 단어가 들어 있다 (W < 10000).

입력은 ENDOFINPUT 줄로 끝난다. 이 줄은 입력의 일부가 아니다.

참고: C보다 긴 단어는 없다.

양쪽 정렬된 줄을 출력한다.

한 줄에 문자는 50개만 있어야 한다. 따라서:

• 첫째 줄은 그 다섯 단어보다 길 수 없었고(공백 포함 49자), 양쪽 정렬을 위해 공백 하나만 추가하면 되었는데, 이는 맨 왼쪽 첫 단어 뒤에 추가되었다.
• 둘째 줄은 32자로 floor(50 / 2) 이상이었으므로, 양쪽 정렬을 위해 공백 19개를 더 추가했다.
• 셋째 줄은 양쪽 정렬되었고, 남은 단어("among the")는 다음 줄로 넘어갔는데, 그 줄은 양쪽 정렬할 수 없다.