cho.shTime limit
5s
Memory limit
16 MB
A DNA sequence is a string made of the bases A, G, C, and T. Decode the sequence by repeatedly shortening it according to the table below until only one base remains.
| A | G | C | T | |
|---|---|---|---|---|
| A | A | C | A | G |
| G | C | G | T | A |
| C | A | T | C | G |
| T | G | A | G | T |
Let the two rightmost bases of the current sequence be X and Y in that order. Replace those two bases with the single base at row X and column Y of the table. Repeat this process until the sequence has length 1.
Given a DNA sequence, output the final base left after decoding it.
The first line contains the length N (1 ≤ N ≤ 1,000,000) of the DNA sequence. The second line contains a DNA sequence of length N.
Print the final decoded base on the first line.