King Bradley has issued Order 3066 allowing the use of State Alchemists (SA) as Human Weapons. The number of Military Police (MP) is same as the number of the SAs. An MP and SA are taken to form a pair and given a code letter based on their skill level using a lowercase English letter. Before the war, all the pairs are arranged in a certain order. (For eg, xyz)
During the war the following strategy is used:
- MPs are released in reverse order. For example, if given order is xyz, they go into battle as zyx.
- SAs are released in a random order. For example, if given order is pqr, they can go in battle as pqr or rpq or prq or qrp, etc.
- Both are released together such that overall order of their releases is maintained. For example, if MPs are coded xyz and SAs are coded pqr (just for the example they are coded diffrently, in reality both will get the same code) they can together go as zyxrpq or rpqzyx or zpryqx or pzyxrq, etc.
Given the order they were ultimately released on the battlefield, find the order they were initially arranged in as pairs keeping it lexicographically the smallest.
Input Format:
A single string containing the final order they were released in.
Constraints:
- Given string contains only lowercase letters.
- Length of the string is <= 10000
Output Format:
A single string containing the original order they were kept in as pairs
If the given initial ordering of the pairs is yzx, then
- MPs will be arranged as xzy.
- One of the arrangements of SA(used here) can be yxz.
- One of the ways of releasing them can be (used here) is yxxzyz.
If the initial ordering is considered as xyz or xzy or yxz, then there is no way we can release them in the order given in the question. Hence the lexicographically smallest possible initial order is yzx.
