Задача 8H. Интересные моменты ≡

Условие

Пётр решил приукрасить свою страницу во ВКонтакте. А именно привести в порядок свои фотографии. Так получилось, что некоторые фотографии у него интересные, а некоторые не очень. И вот Петя решил испробовать методику интересных моментов.

Интересный момент возникает, когда пара интересных фотографий идут друг за другом. То есть, например, трое подряд идущих интересных фотографий создадут 2 интересных момента.

И вот Пётр хочет, чтобы его страница получилась сбалансированной, поэтому просит вас помочь найти количество интересных моментов в его странице, начиная с фотографии номер l до фотографии с номером r.

Пётр ещё в процессе выкладывания фотографий, поэтому иногда он добавляет или удаляет некоторые из них. После каждого из таких его действий нумерация всех фотографий обновляется.

Формат входных данных

В первой строке входных данных располагается число n — количество уже имеющихся фотографий на странице Петра в ВК. (1 ≤ n ≤ 10⁵).

Во второй строке находится последовательность из n нулей и единиц, в которой если на i-й позиции находится единица, то фотография с номером i интересная. И не интересная, если i-й позиции находится ноль.

Далее располагается число q — количество действий Петра (0 ≤ q ≤ 10⁵).

В следующих q строках находится описание действий Петра:

• если строка начинается с символа i, то это означает, что Пётр хочет вставить фотографию. Далее следует два числа p и v. ( − 1 ≤ p ≤ 2 ⋅ 10⁵) — номер фотографии, после которой надо вставить новую. Если p =  − 1, то это означает, что фотографию надо вставить в самое начало. Число v принимает значение 1 или 0 и означает, что новая фотография интересная или не интересная соответственно.
• если строка начинается с символа d, то это означает, что Пётр хочет удалить фотографию. Далее следует одно число p, означающее номер фотографии, которую надо вырвать. (0 ≤ p ≤ 2 ⋅ 10⁵).
• если строка начинается с символа q, то это означает, что Пётр спрашивает вас о количестве интересных моментов на странице. Далее следует два числа l и r. (0 ≤ l ≤ r ≤ 2 ⋅ 10⁵).

Гарантируется, что все заданные номера фотографий существуют на странице (за исключением p =  − 1, но этот случай описан выше).

Нумерация фотографий начинается с нуля.

Формат выходных данных

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

Объяснение примера:

Сначала страница выглядела так: 0111011

Далее тут (0111011) три интересных момента, между 1 и 2 фото, между 2 и 3 фото и между 5 и 6 фото.

Далее тут 01 (11011) два интересных момента.

После этого страница стала выглядеть так: 01101011.

Далее тут (01101011) два интересных момента.

После этого страница стала выглядеть так: 0110111.

Далее тут 0(110111) три интересных момента.

После этого страница стала выглядеть так: 011111.

Далее тут (011111) 4 интересных момента.

После этого страница стала выглядеть так: 11111.

И тут (11111) также 4 интересных момента.

Примеры тестов

7
0111011
10
q 0 6
q 2 6
i 2 0
q 0 7
d 5
q 1 6
d 3
q 0 5
d 0
q 0 4

3 2 2 3 4 4