题目内容

有一个长度为 $n$ 的二进制序列，仅由字符 0 和 1 组成。定义其 评分 为：序列中所有只包含 1 的非空连续子串的个数。

例如，若序列中有一段连续的 1 长度为 $len$，则该段贡献的评分为 $\frac{len(len+1)}{2}$，即 $1+2+\dots+len$。序列的总评分为所有连续 1 段贡献之和。

现在进行 $q$ 次操作，每次操作给出一个位置 $p$，需要将序列第 $p$ 个字符取反（0 变为 1，1 变为 0）。请你求出每次操作后的评分。

序列长度 $n$ 和操作次数 $q$ 均不超过 $2 \times 10^5$，位置 $p$ 满足 $1 \le p \le n$。

输入描述

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \times 10^5$），分别表示序列的长度和操作次数。 第二行包含一个长度为 $n$ 的字符串，仅由字符 0 和 1 组成，表示初始序列。 接下来 $q$ 行，每行包含一个整数 $p$（$1 \le p \le n$），表示将要翻转的位置。

输出描述

输出 $q$ 行，每行一个整数，依次表示每次操作后序列的评分。

样例1

输入

1 2
0
1
1

输出

1
0

说明

初始序列为 0，评分为 0。 第一次操作翻转位置 1，序列变为 "1"，连续 1 段长度 $len = 1$，根据变化量公式 $\Delta = (a+1)(b+1)$，此时左右两侧最近的 0 为哨兵位置 $0$ 和 $2$，得到 $a = 1-0-1 = 0$，$b = 2-1-1 = 0$，评分增加 $(0+1)(0+1)=1$，总评分变为 1。 第二次操作翻转位置 1，序列变回 "0"，同理评分减少 1，总评分变回 0。

样例2

输入

5 3
10101
2
4
3

输出

7
15
6

说明

初始序列 "10101"，有三段长度为 1 的连续 1，每段贡献 $\frac{1 \times 2}{2} = 1$，总评分 3。 第一次操作翻转位置 2（原来是 0），左右最近 0 在位置 $0$ 和 $4$，$a = 2-0-1 = 1$，$b = 4-2-1 = 1$，翻转后合并为长度 $3$ 的连续 1，增加 $(1+1)(1+1)=4$，评分变为 $3+4=7$。 第二次操作翻转位置 4（原来是 0），此时左右最近 0 在位置 $0$ 和 $6$（哨兵），$a = 4-0-1 = 3$，$b = 6-4-1 = 1$，翻转后全部变成 1，长度为 $5$，增加 $(3+1)(1+1)=8$，评分变为 $7+8=15$。 第三次操作翻转位置 3（原来是 1），左右最近 0 在位置 $0$ 和 $6$，$a = 3-0-1 = 2$，$b = 6-3-1 = 2$，翻转后拆分成两段长度 $2$ 的连续 1，减少 $(2+1)(2+1)=9$，评分变为 $15-9=6$。

样例3

输入

6 2
000000
3
4

输出

1
3

说明

初始全为 0，评分为 0。 第一次操作翻转位置 3，该位置原为 0，其左右最近的 0 为位置 2 和 4。左侧连续 1 长度 $a = 3-2-1 = 0$，右侧连续 1 长度 $b = 4-3-1 = 0$。翻转后评分增加 $(0+1)(0+1)=1$，总评分变为 1，序列变为 "001000"。 第二次操作翻转位置 4，此时该位置为 0，其左右最近的 0 变为位置 2 和 5。左侧连续 1 长度 $a = 4-2-1 = 1$（位置 3 是 1），右侧连续 1 长度 $b = 5-4-1 = 0$。翻转后评分增加 $(1+1)(0+1)=2$，总评分变为 $1+2=3$，此时序列为 "001100"，包含一段长度为 2 的连续 1，贡献为 $\frac{2 \times 3}{2}=3$。