У Данила была строка s, состоящая из строчных английских букв и точек (знаков '.'). Определим операцию замены как следующую последовательность действий: найдём подстроку ".." (две подряд идущих точки) в строке s, из всех вхождений этой подстроки выберем самое первое, и заменим эту подстроку на строку ".". Иными словами, во время операции замены первые две подряд идущих точки заменяются на одну. Если в строке s нет двух подряд идущих точек, то ничего не происходит.
Обозначим за f(s) минимальное количество операций замены, которые необходимо произвести, чтобы в строке не осталось двух подряд идущих точек.
Вам требуется обработать m запросов, в результате i-го из них символу на позиции xi (1 ≤ xi ≤ n) строки s присваивается значение ci. После выполнения каждой операции вы должны определить и вывести значение f(s).
Помогите Данилу ответить на все запросы.
Выходные данные
Выведите m чисел по одному в строке, i-е из этих чисел должно равняться значению f(s) после применения i-го присваивания.
Примечание
Пояснение к первому тесту из условия (заменяемые точки окружены квадратными скобками).
Начальная строка — ".b..bz....".
- после первого запроса f(hb..bz....) = 4 ("hb[..]bz...." → "hb.bz[..].." → "hb.bz[..]." → "hb.bz[..]" → "hb.bz.")
- после второго запроса f(hbс.bz....) = 3 ("hbс.bz[..].." → "hbс.bz[..]." → "hbс.bz[..]" → "hbс.bz.")
- после третьего запроса f(hbс.bz..f.) = 1 ("hbс.bz[..]f." → "hbс.bz.f.")
Пояснение ко второму тесту из условия.
Начальная строка — ".cc.".
- после первого запроса: f(..c.) = 1 ("[..]c." → ".c.")
- после второго запроса: f(....) = 3 ("[..].." → "[..]." → "[..]" → ".")
- после третьего запроса: f(.a..) = 1 (".a[..]" → ".a.")
- после четвёртого запроса: f(aa..) = 1 ("aa[..]" → "aa.")
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 3
.b..bz....
1 h
3 c
9 f
|
4
3
1
|
|
2
|
4 4
.cc.
2 .
3 .
2 a
1 a
|
1
3
1
1
|