문자열 문제

Jonathan은 큰 세상의 재미있는 것들을 많이 알고 있다. 오늘 그는 Mavis에게 다음 문제를 냈다. 아마 어떤 정보올림피아드에서 봤거나 다른 곳에서 알았을 것이다.

문자열과, 처음에는 첫 번째 문자를 가리키는 포인터가 있다. 두 가지 연산을 쓸 수 있다.

1. 현재 위치의 문자를 답 문자열 끝에 덧붙인다. 이 위치의 문자를 전에 가져간 적이 없어야 한다. 가져가도 원래 문자는 그 위치에 그대로 남는다.
2. 포인터를 오른쪽으로 한 문자 옮긴다. 현재 문자가 마지막 문자라면 포인터는 문자열의 첫 번째 문자로 돌아간다.

일정 횟수의 연산을 수행한 뒤에는 모든 문자를 가져가야 하고, 답 문자열의 문자가 비내림차순으로 정렬되어 있어야 한다.

예를 들어 문자열이 hello라면 다음과 같이 연산할 수 있다.

1. 두 번째 연산. 포인터를 문자 <<e>>로 옮긴다.
2. 첫 번째 연산. 문자 <<e>>를 가져간다.
3. 두 번째 연산. 포인터를 <<l>>로 옮긴다.
4. 두 번째 연산. 포인터가 <<l>>을 가리킨다.
5. 두 번째 연산. 포인터를 <<o>>로 옮긴다.
6. 두 번째 연산. 포인터가 문자열의 첫 번째 문자 <<h>>를 가리킨다.
7. 첫 번째 연산. <<h>>를 가져간다. 답 문자열은 <<eh>>가 된다.
8. 두 번째 연산. 포인터가 이미 가져간 <<e>>를 가리킨다.
9. 두 번째 연산.
10. 첫 번째 연산. 답은 <<ehl>>이다.
11. 두 번째 연산.
12. 첫 번째 연산. 답은 <<ehll>>이다.
13. 두 번째 연산.
14. 첫 번째 연산. 답은 <<ehllo>>이다.

따라서 첫 번째 종류의 연산을 $5$번, 두 번째 종류의 연산을 $9$번 수행했다.

이 문제를 일반적인 경우로 조금 바꾼 버전을 풀어야 한다.

첫 번째 줄에 소문자 라틴 문자로 이루어진 문자열 $s$ ($1 \le |s| \le 10^5$)가 주어진다. 두 번째 줄에는 질의의 개수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어지는 $m$개의 줄에는 각각 질의의 경계 $l_i$와 $r_i$가 두 정수로 주어진다.

각 질의에 대해, $s$의 $l_i$번째 위치부터 $r_i$번째 위치까지(양 끝 포함) 부분 문자열에서 문제를 풀기 위해 수행해야 하는 두 번째 종류의 연산 횟수를 출력한다.