DNA Decoding

Interview

Time limit5sMemory limit16 MB

Summary

Repeatedly merge the last two bases of a DNA string using a fixed lookup table until one base remains, then output it.

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

Problem

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.

Input

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.

Output

Print the final decoded base on the first line.

Examples1

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