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

Бинарная строка $$$t$$$ длины $$$m$$$ называется чистой, если $$$t_i = t_{i+1}$$$ для всех $$$1\le i\lt m$$$.

Ведущий инженер страны сделал очередное открытие. Он изобрел умного робота, который за одну монету может выполнить следующую операцию на любой бинарной строке $$$t$$$:

  • Выберите любую чистую подстроку$$$^{\text{∗}}$$$ строки $$$t$$$.
  • Инвертируйте все элементы подстроки (поменяйте $$$0$$$ на $$$1$$$ и наоборот).

Определим красоту строки $$$t$$$ как минимальное количество монет, которое требуется потратить, чтобы сделать ее чистой. Силой строки $$$t$$$ назовем сумму красот всех ее подстрок.

Вам дана бинарная строка $$$s$$$ длины $$$n$$$. Конкуренты инженера собираются изменить строку ровно $$$q$$$ раз. Каждое изменение описывается одним числом $$$i$$$. После изменения строки значение $$$s_i$$$ инвертируется. Ваша задача — посчитать силу строки $$$s$$$ до и после каждого изменения.

$$$^{\text{∗}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов с начала и нескольких (возможно, ни одного или всех) символов с конца.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит числа $$$n$$$ и $$$q$$$ ($$$1\le n, q\le 2\cdot 10^5$$$) — длину бинарной строки и количество изменений.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$.

Следующие $$$q$$$ строк каждого набора входных данных содержат по одному числу $$$i$$$ ($$$1\le i\le n$$$) — описание изменений.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходят $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$q + 1$$$ чисел через пробел — ответ до изменений и после каждого изменения строки.

Пример
Входные данные
4
3 1
110
2
4 2
1010
1
2
8 4
10101110
3
5
2
3
10 5
1100101110
1
6
10
7
3
Выходные данные
2 2 
7 5 5 
36 23 22 25 26 
61 66 41 35 59 60
Примечание

Рассмотрим первый набор входных данных.

До изменений строка $$$s$$$ равна 110. Сила строки равна $$$2$$$:

  • Красота подстроки $$$s[1, 1]$$$ равна 0.
  • Красота подстроки $$$s[2, 2]$$$ равна 0.
  • Красота подстроки $$$s[3, 3]$$$ равна 0.
  • Красота подстроки $$$s[1, 2]$$$ равна 0.
  • Красота подстроки $$$s[2, 3]$$$ равна 1.
  • Красота подстроки $$$s[1, 3]$$$ равна 1.
После изменения строка $$$s$$$ равна 100. Теперь сила равна $$$2$$$:
  • Красота подстроки $$$s[1, 1]$$$ равна 0.
  • Красота подстроки $$$s[2, 2]$$$ равна 0.
  • Красота подстроки $$$s[3, 3]$$$ равна 0.
  • Красота подстроки $$$s[1, 2]$$$ равна 1.
  • Красота подстроки $$$s[2, 3]$$$ равна 0.
  • Красота подстроки $$$s[1, 3]$$$ равна 1.