Secret Email

Interview

Time limit1sMemory limit128 MB

Summary

Given an encrypted string, find matrix dimensions R<=C with R*C=N and largest R, then reverse a row-major-write column-major-read transposition to recover the original message.

Level: Easy3 of 10
Topics: Matrix, String, Implementation
Solved: No attempts yet

Problem

Every night, Jungin sends Sanggeun an encrypted email. The original message is a lowercase string of N characters.

Jungin encrypts the message as follows.

Choose two integers R and C such that R <= C and R * C = N. If more than one pair is possible, choose the pair with the largest R.
Create a matrix with R rows and C columns.
Write the original message into the matrix from left to right, starting at the first column of the first row. After a row is full, continue with the next row in the same way.
Read the matrix column by column. In each column, read from the first row down to the R-th row to form the encrypted message.

Given the encrypted message that Sanggeun received, restore Jungin's original message.

Input

The first line contains the encrypted message Sanggeun received. The message consists only of lowercase English letters and has length at most 100.

Output

Print the restored original message on the first line.

Examples3

Example 1
Input
```
bok
```
Expected output
```
bok
```
Example 2
Input
```
koaski
```
Expected output
```
kakosi
```
Example 3
Input
```
boudonuimilcbsai
```
Expected output
```
bombonisuuladici
```