Description

A student JS who enjoys exploring problems has recently become fascinated with encryption methods. One day, he suddenly came up with what he thought was the ultimate encryption method: arrange the message to be encrypted in a circle; obviously, it can be read in many different ways.

For example, 'JSOI07' can be read as: JSOI07, SOI07J, OI07JS, I07JSO, 07JSOI, 7JSOI0. Sort them lexicographically: 07JSOI, 7JSOI0, I07JSO, JSOI07, OI07JS, SOI07J. Read the last column of characters: I0O7SJ, which is the encrypted string (this encryption is actually quite easy to crack, but since it was a sudden idea, just ^^). However, if the string to be encrypted is very long, can you write a program to complete this task?

Input Format

The input contains one line: the string to be encrypted. Note that the string is not necessarily letters or digits; it may also contain symbols, etc.

Output Format

Output one line: the encrypted string.

JSOI07

I0O7SJ

Hint

For $40\%$ of the testdata, the length of the string does not exceed $10^4$.

For $100\%$ of the testdata, the length of the string does not exceed $10^5$.

Translated by ChatGPT 5