Clever Ines

Interview

Time limit1sMemory limit1024 MB

Summary

Reverse a column-by-column reading of an r x s grid (r at most s, r*s = n, r as large as possible) to recover the original message.

Level: Easy2 of 10
Topics: Implementation, String, Math
Solved: No attempts yet

Problem

Ivica sends secret data to little Marica by email every evening. The email passes through several computers on its way to Marica's mailbox, and none of it is protected. They agreed that Ivica encrypts every message with the following algorithm.

Let the message Ivica wants to send Marica consist of $n$ characters.
Ivica first finds a table with $r$ rows and $s$ columns such that $r ≤ s$ and $n = rs$ . If several such tables exist, Ivica picks the one with the most rows.
Ivica writes the message into the table row by row, from top to bottom, and within each row from left to right. The first part of the message goes into the first row, the second part into the second row, and so on.
The message Ivica sends to Marica is read from the table column by column, from left to right, and within each column from top to bottom.

Jealous Ines intercepted an encrypted email that Ivica sent to Marica. Write a program that decrypts the secret message.

Input

The first line contains a string of at least 1 and at most 100 lowercase letters of the English alphabet. This is the encrypted message that Ines intercepted.

Output

Print the decrypted message on a single line.

Examples3

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