B. PSU
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аня только что поступила в новый университет. На первом занятии по программированию ей выдали такую задачку на лабораторную работу.

Имеется строка длиной $$$s$$$, которая состоит только из букв 'P', 'S' или 'U'. Всего имеется $$$q$$$ изменений в этой строке. Каждое изменение меняет ровно одну букву в заданной позиции. Ане необходимо вычислить количество вхождений «PSU» в строке до изменений и после каждого ее изменения.

Задача показалась Ане сложной. Помогите ей с решением этой задачей и сдачей лабораторной, а то скоро сессия!

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

Первая строка входных данных содержит единственное число $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$ - длину строки $$$s$$$.

Вторая строка входных данных содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов 'P', 'S' или 'U'.

Третья строка содержит единственное число $$$q$$$ $$$(1 \le q \le 2\cdot10^5)$$$ - количество изменений в строке.

Далее идут $$$q$$$ строк. Каждая строка содержит позицию изменения $$$pos$$$ $$$(1 \le pos \le n)$$$ и символ $$$c$$$, равный 'P', 'S' или 'U'.

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

Выведите $$$q + 1$$$ число — количество вхождений «PSU» в строку $$$s$$$ до изменений и после каждого изменения.

Пример
Входные данные
6
SPSUSU
4
1 P
3 U
4 P
2 S
Выходные данные
1
1
0
1
2
Примечание

Изначально строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (со $$$2$$$-й позиции).

После первого изменения строка $$$s$$$ станет равна «PPSUSU». Строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (со $$$2$$$-й позиции).

После второго изменения строка $$$s$$$ станет равна «PPUUSU». Теперь, cтрока $$$s$$$ не содержит вхождений «PSU».

После третьего изменения строка $$$s$$$ станет равна «PPUPSU». Строка $$$s$$$ содержит $$$1$$$ вхождение «PSU» (с $$$4$$$-й позиции).

После четвертого изменения строка $$$s$$$ станет равна «PSUPSU». Строка $$$s$$$ содержит $$$2$$$ вхождения «PSU» (с $$$1$$$-й и $$$4$$$-й позиции).