Inverse Burrows–Wheeler Transformation

You are given an encrypted string generated by the following process. Let \(S\) be an original string of length \(N\). Append a special terminator character . (which is lexicographically smaller than any other character) to \(S\) to obtain \(S + .\). Consider the string as a cycle (ring) and generate \(N+1\) rotations by reading \(N+1\) consecutive characters starting at positions 1, 2, \(\dots\), \(N+1\). Then sort the \(N+1\) rotations in lexicographical order. Finally, the encrypted string is obtained by concatenating the last character of each sorted rotation (i.e. the last column of the sorted array).

For example, if \(S = \texttt{ABCAAA}\), we have \(S + . = \texttt{ABCAAA.}\) and the rotations are:

ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA

After sorting lexicographically (remember that . is smaller than any other character), the sorted list is:

.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB

The encrypted string is obtained by taking the last characters of each string in order, resulting in AAAC.AB.

Your task is to recover the original string \(S\) (without the trailing terminator) given the encrypted string.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The input is a single line containing the encrypted string. It is guaranteed to contain exactly one period . which serves as the terminator.

outputFormat

Output the original string before encryption.

sample

AAAC.AB

ABCAAA