Tajna

매일 저녁, 어린 Ivica는 어린 Marica에게 이메일로 비밀 메시지를 보낸다. Ivica의 이메일이 Marica의 메일함으로 가는 길에 아무 보호 없이 네트워크를 지난다는 것을 알기에, 둘은 다음 알고리즘으로 모든 메시지를 암호화하기로 했다:

• Ivica의 메시지가 \(N\)개의 문자로 이루어져 있다고 하자.
• Ivica는 먼저 \(R \le C\)이고 \(R \cdot C = N\)인 \(R\)행 \(C\)열의 행렬을 찾아야 한다. 그런 행렬이 여러 개이면 행이 가장 많은 것을 고른다.
• Ivica는 메시지를 행 우선 순서로 행렬에 적는다. 다시 말해, 메시지의 첫 부분을 첫 행에, 둘째 부분을 둘째 행에 적는 식이다.
• Marica에게 보내는 메시지는 이 행렬을 열 우선 순서로 읽은 것이다.

Marica는 소중한 시간을 Ivica의 메시지 해독에 쓰는 데 지쳐 버렸으니, 그녀를 위해 해독 프로그램을 작성해야 한다.

예를 들어 boudonuimilcbsai(\(16\)글자)를 해독하려면, 행렬은 \(4 \times 4\)이다(\(R \le C\)이고 \(R \cdot C = 16\)인 것 중 행이 가장 많다). 받은 메시지를 열 우선 순서로 채우고 행 우선 순서로 다시 읽으면 원래 메시지 bombonisuuladici가 된다:

b o m b
o n i s
u u l a
d i c i

입력으로 수신한 메시지, 즉 (공백 없는) 영어 알파벳 소문자 문자열이 주어진다. 글자 수는 \(1\) 이상 \(100\) 이하이다.

원래(해독된) 메시지를 출력한다.

riseoj 작성

출처 COCI 2007/2008 Contest 3