Longest reverse palindromic DNA substring As you may know, in DNA there are four bases — adenine (A), cytosine (C), guanine (G) and thymine (T). Typically A bonds with T and C bonds with G, forming the "rungs" of the DNA double helix structure.

We define the complement of a base to be the base it bonds to — i.e. the complement of A is T, the complement of T is A, the complement of C is G and the complement of G is C. We can also define the complement of a DNA string to be the string with each base complemented, e.g. the complement of GATATC is CTATAG.

Because of the double-stranded structure of DNA, the bases on one strand are complementary to the bases on the other strand. However DNA has a direction, and DNA transcription occurs in opposite directions on the two strands. Hence molecular biologists are often interested in the reverse complement of a DNA string — quite literally the reverse of the complement of the string.

To extend our previous example, the reverse complement of GATATC is CTATAG backwards, so GATATC. As you may have noticed, in this example the reverse complement is equal to the original string — we call such a string a reverse palindrome.*

Given a string of DNA, can you find the longest substring which is a reverse palindrome?

*I use the term "reverse palindrome", taken from Rosalind, to differentiate from the usual meaning of palindrome.



Input

Input will be a single string consisting of only the characters ACGT in upper case. You may write either a function or a full program for this challenge.

Output

You may choose to output via either printing or returning (the latter choice is only available in the case of a function).

Your program should output the longest reverse palindromic substring of the input string, if there is a unique solution. If multiple solutions exist, then you may either output any single one of them, or all of them (your choice). Duplicates are okay if you choose to output all of them.

The input is guaranteed to have a solution of at least length 2.

Worked example

ATGGATCCG -&gt; GGATCC


The reverse complement of GGATCC is itself (GGATCC --complement--&gt; CCTAGG --reverse--&gt; GGATCC), so GGATCC is a reverse palindrome. GATC is also a reverse palindome, but it is not the longest one.

Test cases

AT -&gt; AT
CGT -&gt; CG
AGCA -&gt; GC
GATTACA -&gt; AT, TA
ATGGATCCG -&gt; GGATCC
CCCCCGGGGG -&gt; CCCCCGGGGG
ACATATATAGACT -&gt; ATATAT, TATATA
ATTCGATCTATGTAAAGAGG -&gt; TCGA, GATC
CGCACGTCTACGTACCTACGTAG -&gt; CTACGTAG
TCAATGCATGCGGGTCTATATGCAT -&gt; ATGCAT, GCATGC [, ATGCAT]
CGCTGAACTTTGCCCGTTGGTAGAACGGACTGATGTGAACGAGTGACCCG -&gt; CG, GC, TA, AT [, GC, CG, CG, CG, CG]
CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG -&gt; CCGTACGG


Scoring

This is code golf, so the solution in the fewest bytes wins.
Pyth, 37 36 28 24 bytes
ef&amp;}TzqmaCd6T_mx4aCk6Tyz

Combining the tips from FryAmTheEggman and the reverse palindrome check trick from Peter, this is a super short version.
However, this only works with Pyth 3.0.1 which you can download from this link and run like
python3 pyth.py -c &quot;ef&amp;}TzqmaCd6T_mx4aCk6Tyz&quot; &lt;&lt;&lt; &quot;ATTCGATCTATGTAAAGAGG&quot;

(linux bash only. On windows, press Enter instead of the &lt;&lt;&lt; and then type the input)

This is my previous submission - 28 bytes solution
J&quot;ACGT&quot;ef&amp;}TzqTjk_m@_JxJdTyz

Thanks to FryAmTheEggman for this version. This one creates all possible subsets of the input DNA string, filters the subsets on the condition that the subset is a substring of input and the reverse of transform is equal to the subset itself.
Due to all possible subset creation, this takes up even more memory than Peter's answer.

This is my first submission - 36 byte solution.
J&quot;ACGT&quot;eolNfqTjk_m@_JxJdTm:zhkek^Uz2

This is the exact translation of my CJam answer. I was hoping that this would be much smaller but turns out that lack of translation method made it almost similar size (still 2 bytes smaller though)
Try it online here