409504: GYM103585 K Ceiba Tree

Groot, Rocket Raccoon's personal muscle in the Guardians of the Galaxy, is a special variant of the ceiba tree. Scientists at Stark Enterprises are curious as to how the resilient Flora colossus survived with its genetic material completely preserved throughout "The Blip". The sentient ceiba tree is more than happy to provide a piece of bark for the lab technicians to analyze; however, the genetic material of ceiba trees is circular in nature, which makes it difficult to compare samples due to rotational possibilities. Petra, the head of lab tech, decided to store data on samples based on a rather odd convention (due to boredom from integer hashing).

Each ceiba tree sample can be represented as a string $$$G$$$ of $$$N$$$ lowercase alphabetical characters. The representation of the sample that will be deterministically stored for a given string is based on the integer $$$1 \leq i < N$$$ that creates the lexicographically maximal concatenation of the reversed first $$$i$$$ characters of $$$G$$$ and the reversed last $$$N-i$$$ characters of $$$G$$$. Although Petra came up with this idea, she actually has no idea how to efficiently compute the stored representation for large amounts of samples. You, the new intern, are tasked with writing a program to help the senior lab member with her deliverables.

The first and only line of input will contain a single string $$$G$$$ as described above. It will be at most $$$10^6$$$ characters long.

Output a single line with the stored representation of $$$G$$$.

groot

rgtoo

bzyaa

zbaay