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

У Данила была строка s, состоящая из строчных английских букв и точек (знаков '.'). Определим операцию замены как следующую последовательность действий: найдём подстроку ".." (две подряд идущих точки) в строке s, из всех вхождений этой подстроки выберем самое первое, и заменим эту подстроку на строку ".". Иными словами, во время операции замены первые две подряд идущих точки заменяются на одну. Если в строке s нет двух подряд идущих точек, то ничего не происходит.

Обозначим за f(s) минимальное количество операций замены, которые необходимо произвести, чтобы в строке не осталось двух подряд идущих точек.

Вам требуется обработать m запросов, в результате i-го из них символу на позиции xi (1 ≤ xi ≤ n) строки s присваивается значение ci. После выполнения каждой операции вы должны определить и вывести значение f(s).

Помогите Данилу ответить на все запросы.

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

В первой строке находятся два целых числа n и m (1 ≤ n, m ≤ 300 000) — длина строки и количество запросов.

Во второй строке следует строка s, состоящая из n строчных английских букв и точек.

В последующих m строках следуют описания запросов. В i-й строке находятся целое число xi и ci (1 ≤ xi ≤ n, ci — строчная латинская буква или точка), описывающие запрос присваивания символа ci на позицию xi.

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

Выведите m чисел по одному в строке, i-е из этих чисел должно равняться значению f(s) после применения i-го присваивания.

Примеры
Входные данные
10 3
.b..bz....
1 h
3 c
9 f
Выходные данные
4
3
1
Входные данные
4 4
.cc.
2 .
3 .
2 a
1 a
Выходные данные
1
3
1
1
Примечание

Пояснение к первому тесту из условия (заменяемые точки окружены квадратными скобками).

Начальная строка — ".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.")