JB 正在尝试在他的 AC 自动机上获得更多的 “AC”。

AC 自动机是一棵有 $n$ 个节点的有根树，节点 1 为根。除了根节点外，每个节点 $i$ 都有一个唯一的父节点 $p_i$ 和一个字符 $s_i$，字符为 ‘A’、‘C’ 或 ‘?’ 中的一个。当且仅当 $x = p_y$ 或 $x$ 是 $p_y$ 的祖先时，称节点 $x$ 为 $y$ 的祖先。JB 能获得的 “AC” 数量等于满足 $x$ 是 $y$ 的祖先、$s_x = \text{‘A’}$ 且 $s_y = \text{‘C’}$ 的有序对 $(x, y)$ 的数量。JB 可以将 ‘?’ 任意替换为 ‘A’ 或 ‘C’。他的目标是在替换所有 ‘?’ 后获得尽可能多的 “AC”。

然而，问题总是在变化。JB 将会对他的 AC 自动机进行 $q$ 次修改。每次修改，他会将某个节点 $x$ 上的字符修改为 ‘A’、‘C’ 或 ‘?’ 中的一个（字符可能不会改变）。JB 希望你在每次修改后，回答他在替换所有 ‘?’ 后能获得的 “AC” 的最大数量。注意，JB 在计算 “AC” 的最大数量时，并不会真正修改 AC 自动机。你可以参考样例来帮助理解。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 300\,000$)。

第二行包含一个长度为 $n$ 的字符串，表示每个节点上的字符。保证字符串中的字符均为 ‘A’、‘C’ 或 ‘?’。

第三行包含 $n - 1$ 个整数，第 $i$ 个整数 $p_i$ ($1 \le p_i \le i$) 表示节点 $i + 1$ 的父节点。

接下来的 $q$ 行描述修改操作。第 $i$ 行包含一个整数 $x$ ($1 \le x \le n$) 和一个字符 $y$ ($y \in \{\text{‘A’, ‘C’, ‘?’}\}$)，表示一次修改。

输出格式

输出 $q$ 行。

在第 $i$ 行，输出一个整数，表示第 $i$ 次修改后能获得的 “AC” 的最大数量。

样例

输入 1

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

输出 1

4
3
3

说明

第一次修改后，替换字符的最佳方式之一是 “ACCCC”，此时有 4 对 $(1, 2), (1, 3), (1, 4)$ 和 $(1, 5)$。

第二次修改后，替换字符的最佳方式之一是 “ACCAC”，此时有 3 对 $(1, 2), (1, 3)$ 和 $(1, 5)$。

第三次修改后，替换字符的最佳方式之一是 “AACAC”，此时有 3 对 $(1, 3), (2, 3)$ 和 $(1, 5)$。