The National Organisation of Illegal Activities and Whatever not (NOI) is back, and this time it wishes to uncover Barr the bear's deepest darkest secrets! However, ever the cunning one, Barr the bear has obfuscated all secret information he has on him and kept them safely on tiny pieces of paper in a jar.
With some luck and a bit of skill, the NOI has managed to steal Barr's jar and figure out Barr's method of obfuscation. It goes like this:
- Suppose Barr's message consists of N characters.
- Barr first finds a matrix consisting of R rows and C columns such that R ≤ C and R*C = N. If there is more than one such matrix, he chooses the one with the most rows.
- Barr 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 writes on the piece of paper is the matrix read in column-major order.
Now, the NOI has hired you to help them find out Barr's original messages in the jar!
The input contains Barr's obfuscated message, a string of lowercase letters of the English alphabet (with no spaces).
The number of letters will be between 1 and 100.
Output Barr's original message.
Sample Input 1
Sample Output 1
Explanation for Sample Output 1
Barr's secret message is "ilikehoney" containing 10 letters. He can use a 1x10 or 2x5 matrix. Of these, the 2x5 has the most rows. When the message is written into it, the matrix looks like this: