Lexicographically Minimal Reversed Partition

Given a non-empty string S, partition it into three non-empty segments S₁, S₂ and S₃ such that S = S₁ || S₂ || S₃. For each partition, reverse every segment individually to obtain S₁^R, S₂^R, and S₃^R, and then concatenate the results in the original segment order.

Since there are multiple possible ways to partition the string, you are required to select the one that yields the lexicographically smallest resultant string. Formally, if a candidate output corresponding to a partition is given by:

then among all valid partitions, choose the candidate output such that

where the minimum is taken in dictionary (lexicographic) order.

inputFormat

The input consists of a single line containing the string S to be partitioned. The string contains only visible ASCII characters and its length is at least 3.

Format:

S

outputFormat

Output the lexicographically smallest string that can be obtained by reversing each of the three segments (obtained by any valid partition of S) and concatenating them in order.

Format:

result

sample

abc

abc