29046번 - Задачка о строке 다국어

문제

Джонатан знает много забавных вещей из большого мира. Сегодня он задал Мэйвис следующую задачку (наверное, он знает ее с какой-нибудь олимпиады по информатике, а может и еще откуда-нибудь):

Есть строка, а также указатель, который изначально указывает на первый символ строки. Доступны две операции:

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$-й включительно.

제한

힌트