아르네 사크누셈

쥘 베른의 이야기에 따르면, 중세의 연금술사 아르네 사크누셈이 쓴 뒤섞인 메시지를 리덴브로크 교수가 해독하면서 지구 중심으로의 놀라운 여행이 시작되었다. 아르네가 사용한 뒤섞기 절차는 아래에 설명하는 것과 비슷하다.

1. 영어 알파벳 문자, 숫자, 쉼표, 마침표, 작은따옴표(즉 '), 공백, 줄바꿈으로 이루어지고 마지막 문자가 공백이 아닌, 비어 있지 않은 메시지 $M$을 준비한다. 예를 들어 다음 메시지를 생각해 보자. 이 메시지를 번역하면 "In Sneffels's crater descend brave traveler, and touch the center of the Earth"이다.

In Sneffels craterem descende audas
viator, et terrestre centrum attinges.

2. 정수 $0 < K \le \operatorname{length}(M)$을 하나 고르고, 결과 메시지 $M'$의 길이가 $K$의 배수 중 가장 작은 값이 되도록 $M$의 뒤에 공백을 덧붙인다. 위 메시지에서 $\operatorname{length}(M) = 74$($M$에 포함된 공백 8개와 줄바꿈 1개를 포함)이고 $K = 19$일 때, 공백 2개가 뒤에 덧붙어 $\operatorname{length}(M') = 76$인 $M'$이 만들어진다.

3. $M'$의 모든 공백을 문자 _(밑줄)로 바꾸고, 모든 줄바꿈을 \(역슬래시)로 바꾼 뒤, 메시지를 뒤집는다. 이 예에서는 다음과 같다.

__.segnitta_murtnec_ertserret_te_,rotaiv\sadua_ednecsed_meretarc_sleffenS_nI

4. 3단계에서 만들어진 메시지를 $\operatorname{length}(M') / K$개의 행과 $K$개의 열을 가진 표에 적는다. 적는 방향은 열 단위(위에서 아래로 한 열씩)이다. 이 예에서는 $76 / 19 = 4$개의 행과 $19$개의 열을 가진 표에 다음과 같이 적힌다.

5. 표의 각 행에 해당하는 문자열들이 뒤섞인 메시지의 조각이다. 1단계에 있는 아르네 메시지의 조각 4개는 다음과 같다.

_etmneet_t\udsmt_fS _gtuerr_,asaneeasf_
.narctrtria_edrrlen si_t_seeovdec_ecenI

위와 같이 뒤섞인, 비어 있지 않은 메시지를 해독하는 프로그램을 작성하라. 뒤섞기 전 메시지의 길이는 공백과 줄바꿈을 포함하여 최대 $1000$자이다.

프로그램의 입력은 텍스트 파일에서 읽으며, 각 데이터 집합은 하나의 뒤섞인 메시지에 해당한다. 하나의 데이터 집합은 뒤섞인 메시지의 조각 개수를 나타내는 정수 $n$으로 시작하고, 이어서 뒤섞기 절차의 4단계 표에 나타나는 순서대로 조각을 나타내는 $n$개의 문자열이 온다. 입력 데이터는 공백 문자로 구분되며 파일의 끝에서 종료된다.

해독된 메시지는 표준 출력에 줄의 처음부터 출력해야 하며, 아래의 입출력 예제에서 보이는 것처럼 그 뒤에 빈 줄이 하나 와야 한다.