DNA 해독 2
시간 제한1초메모리 제한2 MB
최대 2천만 길이의 DNA 문자열에서 오른쪽 두 글자를 표에 따라 계속 합쳐 한 글자가 남을 때까지 축소하는 문제입니다.
문제
DNA 염기서열은 A, G, C, T로 이루어진 문자열이다. 이 서열을 아래 해독표에 따라 한 글자가 남을 때까지 줄인다.
현재 서열의 오른쪽 끝 두 염기를 차례로 X, Y라고 하자. 두 글자 XY를 표에서 X 행과 Y 열이 만나는 칸의 염기 하나로 바꾼다. 이 과정을 길이가 1이 될 때까지 반복한다.
주어진 염기서열을 해독했을 때 마지막에 남는 염기를 출력하라.
입력
첫째 줄에 염기서열의 길이 N (1 ≤ N ≤ 20,000,000)이 주어진다.
둘째 줄에 길이가 N이고 A, G, C, T로만 이루어진 염기서열이 주어진다.
출력
첫째 줄에 최종 염기 하나를 출력한다.