Олимпиадный тренинг

Задача . B. Илья и запросы


Задача

Темы: реализация дп *1100

Лев Илья хочет помочь всем своим друзьям со сдачей экзаменов. Чтобы сдать экзамен по информатике нужно решить следующую задачу.

Даны строка s = s1s2... sn (n — длина строки), состоящая только из символов «.» и «#», и m запросов. Каждый запрос описывается парой целых чисел li, ri (1 ≤ li < ri ≤ n). Ответ на запрос li, ri — это количество таких целых чисел i (li ≤ i < ri), что si = si + 1.

Лев Илья хочет помочь друзьям, но кто же поможет ему. Помогите Льву Илье, решите задачу.

Входные данные

В первой строке записана строка s длины n (2 ≤ n ≤ 105). Гарантируется, что заданная строка состоит только из символов «.» и «#».

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов. В каждой из следующих m строк записано описание соответствующего запроса. В i-той строке записаны целые числа li, ri (1 ≤ li < ri ≤ n).

Выходные данные

Выведите m целых чисел — ответы на запросы в том порядке, в котором запросы заданы во входных данных.


Примеры
№Входные данныеВыходные данные
1 
......
4
3 4
2 3
1 6
2 6
 
1
1
5
4
2 
#..###
5
1 3
5 6
1 5
3 6
3 4
 
1
1
2
2
0

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет