DNA 해독

DNA 염기서열은 A, G, C, T로 이루어진 문자열이다. 이 염기서열을 아래 해독표에 따라 한 글자가 남을 때까지 줄이려고 한다.

현재 염기서열의 오른쪽 끝 두 염기를 차례대로 X, Y라고 하자. 표에서 X가 있는 행과 Y가 있는 열이 만나는 칸의 염기 하나로 두 염기를 바꾼다. 이 과정을 염기서열의 길이가 1이 될 때까지 반복한다.

주어진 염기서열을 해독했을 때 마지막에 남는 염기를 출력하라.

첫째 줄에 염기서열의 길이 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 길이가 N인 염기서열이 주어진다.

첫째 줄에 최종 염기 하나를 출력한다.