题目描述

多年以后，⾯对低矮的树墩， 指挥官总会回想起那个他和他的部下攻克宫⽩的那个遥远的下午。 战⽕烧遍⼤地，就连警⻋也不放过，这棵站在宫⽩前的树也是⼀样。 “我曾⽤望远镜⽆意间看过它⼀眼，没想到竟是最后⼀眼”， 指挥官如此说道。 “我还记得它⻓什么样！！！”，第三炮兵部队总司令报告。 但是，很可惜，炮⻓的记忆⼒属实有点逊，但是 指挥官并不关⼼树的具体形态，他定义了如下⼀个 值来表⽰树的外观： $$Sum = \sum_{\text{x is y's ancestor}} [C_x=\text{A}][C_y=\text{B}]$$ 其中 表⽰树上 节点的颜⾊，⼀颗树不会有很多种颜⾊，所以只有 A 和 C 两种，但是有的节点的颜⾊ 不确定，那就是 ? ，即可能是 A 也可能是 C 。 指挥官只想知道在所有可能情况中 $Sum$ 的最⼤值。 然⽽，炮⻓是个善变的⼈，他每秒都会报告⼀次，每次报告形如 节点的颜⾊是 A 、 C 、 ? 中哪⼀个。 但是，指挥官却突然想知道每次炮⻓报告之后树的最⼤可能值。

输入格式

第⼀⾏两个数 $n,q$。 第⼆⾏⼀个⻓为 $n$ 的字符串，从左往右数第 $i$ 个字符 $C_i$ 表⽰节点 $i$ 上的字符。 第三⾏ $n-1$ 个整数，第 $i$ 个表⽰节点 $i+1$ 的⽗亲节点 。 接下来 $q$ ⾏，每⾏⼀个整数 $i$ 与字符 $c$，表⽰ $i$ 节点的字符替换为 $c$。

输出格式

共 $q$ ⾏，代表每次修改后的答案。

【样例 1 输⼊】

5 3
AC??C
1 2 2 1
1 ?
4 A
2 ?

【样例 1 输出】

4
3
3

【测试点约束】

对于所有数据，$1\le n,q\le 1.5\times 10^5$。

每个⼦任务的具体约束⻅下表。