뉴클레오타이드 분포 구하기

Genes 'R Us는 DNA 가닥을 분석해서 이상 징후, 일치하는 부분, 패턴, 또는 고객이 원하는 특정 항목을 찾는 회사이다. 고등학교 생물 시간에 배웠듯이 DNA 분자는 두 가닥이 서로 감겨 이중 나선을 이룬다. 각 가닥은 질소 염기로 구분되는 네 종류의 뉴클레오타이드로 이루어진다: 아데닌(A), 티민(T), 구아닌(G), 시토신(C).

Genes 'R Us의 최근 고객은 DNA의 주어진 구간에서 어떤 뉴클레오타이드가 가장 많은지, 그리고 두 번째, 세 번째, 네 번째로 많은 것이 무엇인지 빠르게 알고 싶어 한다. 가닥에는 수만 개의 뉴클레오타이드가 있을 수 있고, 같은 가닥의 여러 구간에 대해 질문이 반복된다. 이 질문에 답하는 효율적인 프로그램을 작성하는 것이 과제다.

첫 줄에는 DNA 가닥을 나타내는 문자열이 주어진다. 문자열은 A, T, G, C 문자로만 이루어지며, 길이 $n$은 $n \leq 50\,000$을 만족한다. 다음 줄에는 조사할 구간의 개수 $m$($m \leq 25\,000$)이 양의 정수로 주어진다. 이어서 $m$개의 줄에 각각 구간의 시작 위치 $s_i$와 끝 위치 $e_i$가 정수 쌍으로 주어지며, $1 \leq s_i \leq e_i \leq n$이다. 정수 쌍은 공백 한 칸으로 구분된다.

각 구간마다 ATGC의 순열을 한 줄에 출력한다. 첫 글자는 그 구간에서 가장 많이 나타나는 뉴클레오타이드이고, 두 번째 글자는 두 번째로 많은 뉴클레오타이드이며, 이후도 같은 방식이다. 개수가 같으면 ATGC 순서로 정한다. 즉 개수가 같을 때 A는 T, G, C보다 앞에 오고, T는 G, C보다 앞에 온다.