C. Игра с монетами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть несколько монет, расположенных в ряд, пронумерованных от $$$1$$$ слева направо. Существует три типа монет: золотые, серебряные и бронзовые.

Два игрока играют в игру; игроки ходят по очереди, и первый игрок делает первый ход. За один ход игрок выбирает любой из трех типов монет и забирает все монеты этого типа, которые еще не забрал другой игрок, себе. Игра продолжается до тех пор, пока все монеты не будут собраны. Оба игрока играют оптимально, и каждый из них хочет максимизировать количество монет, которое он получит.

Ваша задача — ответить на $$$q$$$ независимых запросов следующего вида: сколько монет может собрать первый игрок, если игра ведется только с монетами с индексами от $$$l$$$ до $$$r$$$ включительно.

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

Первая строка содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящую из символов G, S и/или B. G означает, что монета золотая. S означает, что монета серебряная. B означает, что монета бронзовая.

Вторая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Далее следуют $$$q$$$ строк; каждая из них содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le |s|$$$).

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

Для каждого запроса выведите одно целое число — количество монет, которые может собрать первый игрок, если игра ведется только с монетами с индексами от $$$l$$$ до $$$r$$$ включительно.

Пример
Входные данные
BGSSBGB
5
1 7
2 6
1 5
3 3
4 7
Выходные данные
5
3
3
1
3
Примечание

Рассмотрим запросы из примера:

  • в первом запросе в игре все монеты. Оптимальная игра может идти так: первый игрок забирает все бронзовые монеты, второй — все золотые, и наконец, первый — все серебряные. Тогда первый игрок заберет $$$5$$$ монет;
  • во втором запросе в игре монеты со $$$2$$$-й по $$$6$$$-ю. Оптимальная игра может идти так: первый игрок забирает все серебряные монеты, второй — все золотые, и наконец, первый — все бронзовые. Тогда первый игрок заберет $$$3$$$ монеты;
  • в третьем запросе в игре монеты с $$$1$$$-й по $$$5$$$-ю. Оптимальная игра может идти так: первый игрок забирает все серебряные монеты, второй — все бронзовые, и наконец, первый — все золотые. Тогда первый игрок заберет $$$3$$$ монеты;
  • в четвертом запросе в игре только $$$3$$$-я монета. Первый игрок может сразу же забрать ее и закончить игру.