알고리즘 시험문제인데 문제는 좋은거 같은데 아무리 풀어도 못풀겠어서 질문드립니다. 화면에 입력예시와 출력예시처럼 만들면 됩니다.

입력조건 첫 줄에는 두자연수가 N Q형식으로 주어진다. N은 전시되어 있는 책의 권수를 나타내는 10만이하의 자연수이다. Q는 동이가 조사할 구간의 수를 나타내는 20만이하의 자연수이다.

두 번쨰 줄에는 책들이 놓여진 순서대로 각 책의 첫 글자만을 이어붙여 만든 N근자의 문자열이 주어진다. *각 줄은 L R형식의 두 자연수로 구성된다. L은 항상 R의하의 값을 가진다. *L은 동이가 조사하고자 하는 연속된 구간에서 왼쪽 끝에 있는 책의 번호를 나타낸다. *R은 동이가 조사하고자 하는 연속된 구간에서 오른쪽 끝에 있는 책의 번호를 나타낸다.

출력 조건 동이가 조사하고자 하는 Q개의 구간에 대하여 각각 한줄에 정답을 출력한다.

*책 제목의 첫 글자로 가장 많이 등장한 알파벳을 출력한다. *등장횟수가 같은 알파벳이 여러개라면 사전순으로 가장 앞서는 알파벳을 출력한다.

입력 예시 15 5

AAAABBBBBCCDEFG

4 5

3 4

9 10

3 6

1 15

출력 예시

B

A

B

A

B