Every evening, little Ivica sends secret messages to little Marica through e-mail. Knowing Ivica’s e-letter travels unguarded through the network on its way to Marica’s e-mailbox, they have decided to encrypt every message using the following algorithm:
Suppose Ivica’s message consists of $N$ characters.
Ivica must first find a matrix consisting of $R$ rows and $C$ columns such that $R \le C$ and $R \cdot C = N$. If there is more than one such matrix, Ivica chooses the one with the most rows.
Ivica writes his message into the matrix in row-major order. In other words, he writes the first segment of the message into the first row, the second segment into the second row and so on.
The message he sends to Marica is the matrix read in column-major order.
For instance, suppose Ivica wants to send the message “bombonisuuladici” containing 16 letters. He can use a $1 \times 16$, $2 \times 8$, or $4 \times 4$ matrix. Of these, the $4 \times 4$ has the most rows. When the message is written into it, the matrix looks like this, and the encrypted message becomes “boudonuimilcbsai”.
b |
o |
m |
b |
o |
n |
i |
s |
u |
u |
l |
a |
d |
i |
c |
i |
Marica has grown tired of spending her precious time deciphering Ivica’s messages, so you must write a program to do it for her.
The input contains the received message, a string of lowercase letters of the English alphabet (with no spaces). The number of letters will be between 1 and 100.
Output the original (decrypted) message.
Sample Input 1 | Sample Output 1 |
---|---|
bok |
bok |
Sample Input 2 | Sample Output 2 |
---|---|
koaski |
kakosi |
Sample Input 3 | Sample Output 3 |
---|---|
boudonuimilcbsai |
bombonisuuladici |