Вам задана строка \(s\), состоящая из строчных букв латинского алфавита и \(q\) запросов к этой строке.
Напомним, что подстрокой \(s[l; r]\) строки \(s\) называется строка \(s_l s_{l + 1} \dots s_r\). Например, подстроками «codeforces» являются «code», «force», «f», «for», но не строки «coder» и «top».
Всего существует два вида запросов:
Первая строка входных данных содержит одну строку \(s\), состоящую из не более, чем \(10^5\) строчных букв латинского алфавита.
Вторая строка входных данных содержит одно целое число \(q\) (\(1 \le q \le 10^5\)) — количество запросов.
Следующие \(q\) строк содержат запросы, по одному в строке. Каждый запрос задан в формате, описанном в условии задачи. Гарантируется, что есть хотя бы один запрос второго типа.
На каждый запрос второго типа выведите ответ на него — количество различных символов в подстроке, заданной в этом запросе.
abacaba 5 2 1 4 1 4 b 1 5 b 2 4 6 2 1 7
3 1 2
dfcbbcfeeedbaea 15 1 6 e 1 4 b 2 6 14 1 7 b 1 12 c 2 6 8 2 1 6 1 7 c 1 2 f 1 10 a 2 7 9 1 10 a 1 14 b 1 1 f 2 1 11
5 2 5 2 6
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач