Optimized Genetic Sequence Folding

International Cell Processing Company (ICPC) has discovered a novel process called Genetically Optimized Organic Folding (GOOF), which transforms a nucleotide sequence into a shorter sequence while preserving many of its key properties. A nucleotide sequence is represented by a string containing only the letters A, C, G, and T.

A fold operation is defined as follows. Given a sequence S of length n, choose an index i (1 ≤ i < n) and split S into two parts: L = S[0...i-1] and R = S[i...n-1]. The fold is valid if for every k from 1 to min(|L|,|R|) the following condition holds: $$ S[i-k] = S[i+k-1] $$ In other words, the k-th nucleotide from the end of L must equal the k-th nucleotide from the beginning of R.

If the fold is valid, there are two folding options:

• If |L| ≤ |R|, one option produces the new sequence equal to R, and the other produces the new sequence equal to \(R^R\) (the reversal of R).
• If |L| > |R|, one option produces the new sequence equal to L, and the other produces the new sequence equal to \(L^R\) (the reversal of L).

You may apply the folding operation repeatedly until no further valid folds exist. Your task is to determine the shortest possible genetic sequence that can be obtained by a (possibly empty) sequence of valid fold operations. If there are multiple results with the minimal length, output the lexicographically smallest one.

inputFormat

The input consists of a single line containing the genetic sequence S, which is a non-empty string consisting only of the characters A, C, G, and T.

outputFormat

Output the shortest possible genetic sequence obtainable by repeatedly applying valid fold operations. If multiple sequences of minimal length exist, output the lexicographically smallest one.

sample

ATTACC

CAT