cho.shTime limit
1s
Memory limit
2 MB
A DNA sequence consists only of the bases A, G, C, and T. Reduce the sequence according to the decoding 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 the two-character suffix XY with the single base found at row X and column Y of the table. Repeat this process until the sequence has length 1.
Given the DNA sequence, output the final base that remains after decoding.
The first line contains the length N of the DNA sequence (1 ≤ N ≤ 20,000,000).
The second line contains a DNA sequence of length N consisting only of A, G, C, and T.
Output the final remaining base on the first line.