DNA 해독 2

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

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

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

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

둘째 줄에 길이가 N이고 A, G, C, T로만 이루어진 염기서열이 주어진다.

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