DNA Decoding 2

Time limit1sMemory limit2 MB

Summary

Given a DNA string up to 20 million bases, repeatedly collapse the rightmost two characters using a lookup table until one base remains.

Level: Easy3 of 10
Topics: String, Simulation, Implementation
Solved: No attempts yet

Problem

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.

Input

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

Output the final remaining base on the first line.

Examples1

Example 1
Input
```
6
AAGTCG
```
Expected output
```
A
```