Matrix Transposition Encryption

Given a plaintext string, encrypt it using the following algorithm.

Let the length of the string be \(n\). Determine two positive integers \(r\) and \(c\) such that \(r \times c = n\) and \(r \le c\), while \(r\) is as large as possible. In other words, among all factor pairs of \(n\) satisfying \(r \le c\), choose the pair with the maximum \(r\).

Next, fill an \(r\times c\) matrix with the characters of the plaintext in column-major order (i.e. filling each column from top to bottom, moving from the leftmost column to the rightmost column).

The ciphertext is then produced by reading the matrix in row-major order (i.e. reading each row from left to right, starting from the top row).

For example, if plaintext is abcdefghi (with \(n=9\)) then the matrix will be:

[ \begin{matrix} a & d & g
b & e & h
c & f & i \end{matrix} ]

and the resulting ciphertext will be adgbehcfi.

inputFormat

The input consists of a single line containing the plaintext string. The length of the string \(n\) is guaranteed to have at least one factor pair \((r, c)\) satisfying \(r \times c = n\) with \(r \le c\).

outputFormat

Output the ciphertext string generated by applying the encryption algorithm described above.

sample

abcdef

acebdf