똑똑한 아이네스

면접 대비

시간 제한1초메모리 제한1024 MB

요약

암호문을 r x s 표에 열 순서로 채운 뒤 행 순서로 읽어 원래 메시지를 복원합니다. r은 r ≤ s, rs = n을 만족하는 가장 큰 값입니다.

문제

이보는 매일 저녁 어린 마리차에게 이메일로 비밀 데이터를 보낸다. 이 메일은 마리차의 메일함에 도착하기까지 여러 컴퓨터를 거치며, 그동안 아무런 보호도 받지 않는다. 그래서 두 사람은 이보가 다음 알고리즘으로 모든 메시지를 암호화하기로 합의했다.

이보가 마리차에게 보내려는 메시지의 길이를 $n$ 글자라고 하자.
이보는 먼저 $r ≤ s$ 이고 $n = rs$ 를 만족하는 $r$ 행 $s$ 열의 표를 찾는다. 그런 표가 여러 개라면 행의 수가 가장 많은 표를 고른다.
이보는 메시지를 표에 위에서 아래로 행 단위로 적는다. 각 행은 왼쪽에서 오른쪽으로 적는다. 메시지의 첫 부분은 첫 번째 행에, 둘째 부분은 두 번째 행에 적는 식이다.
이보가 마리차에게 보내는 메시지는 표를 왼쪽에서 오른쪽으로 열 단위로 읽어서 얻는다. 각 열은 위에서 아래로 읽는다.

질투 많은 아이네스가 이보가 마리차에게 보낸 암호화된 이메일을 가로챘다. 비밀 메시지를 복호화하는 프로그램을 작성하라.

첫 줄에 아이네스가 가로챈 암호화된 메시지인, 영어 소문자로 이루어진 길이 1 이상 100 이하의 문자열이 주어진다.

복호화한 메시지를 한 줄에 출력한다.